[BAEKJOON/Python3] 백준 1920 수 찾기

https://www.acmicpc.net/problem/1920

1920번: 수 찾기

＊링크로 접속하여 문제를 확인할 수 있습니다.

 

문제 설명

첫째 줄에 N, 둘째 줄의 N개의 숫자가 주어지고, 세번째 줄에 M, 네번째 줄에 M개의 숫자가 주어질 때, M개의 숫자 각각이 N개의 숫자의 배열인 A에 존재하는지를 확인하는 문제이다.

M개의 숫자 각각을 리스트 A에서 찾고, 존재하면 1, 존재하지 않으면 0을 한줄씩 출력해야 한다.

 

코드

def findA(list,num):
    right = len(list)-1
    left = 0
    while left <= right:
        mid = (right + left) // 2
        if list[mid] > num:
            right = mid - 1
        elif list[mid] < num:
            left = mid + 1
        else:
            return True
    return False


N = int(input())
A = list(map(int,input().split()))
A.sort()

M = int(input())
B = list(map(int,input().split()))
for i in range(M):
    if findA(A,B[i]):
        print(1)
    else:
        print(0)

위와 같이 코드를 작성했다.

우선 정수형 N을 입력받고, A라는 리스트에 N개의 숫자를 정수형으로 입력받아 저장했다. 이분 탐색을 이용할 것이기 때문에 우선 A를 오름차순으로 정렬시키기 위해 sort 함수를 이용했다.

정수형 M을 입력받고, B 리스트에 마찬가지로 M개의 숫자를 저장했다. 그리고 M개의 숫자 각각을 findA 함수에 넣어 결과가 True라면 1을 출력하도록, False라면 0을 출력하도록 했다.

 

findA 함수는 간단한 이분 탐색 방법으로, 처음에는 left는 0으로, right는 N-1로 설정했다. 그리고 right가 left보다 작아지면 반복문을 종료하고 수가 없는 것으로 판단하고 false를 반환하도록 했다. right가 left보다 크다면 계속 다음과 같은 과정을 반복한다.

1. mid는 left와 right를 더한 후 2로 나눈 몫으로 설정

2. mid 위치에 있는 숫자가 찾고 있는 수보다 크다면 : 왼쪽 반쪽을 탐색하기 위해 right를 mid-1로 업데이트

3. mid 위치에 있는 숫자가 찾고 있는 수보다 작다면 : 오른쪽 반쪽을 탐색하기 위해 left를 mid+1로 업데이트

4. 모두 아니라면 mid 위치에 있는 수가 찾고 있는 수와 일치한다는 뜻이기 때문에 존재한다는 뜻으로 True를 반환

 

리스트에서 in 과 같은 함수를 이용한다면 문제를 해결할 수 있지만 최대 리스트 전체를 탐색해야 하기 때문에 시간복잡도가 O(n)으로 오래 걸린다는 문제가 있다. 이분 탐색을 이용하면 전체를 탐색하지 않고 절반씩 나누어 탐색하기 때문에 시간 복잡도가 O(log n)으로 줄어들어 탐색 시간을 줄일 수 있다.