[CodingTest] 백준 #1920 수 찾기

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

1920번: 수 찾기

 

내 풀이

import sys
n=int(sys.stdin.readline())
arr_n = list(map(int,sys.stdin.readline().split()))
m=int(sys.stdin.readline())
arr_m = list(map(int,sys.stdin.readline().split()))
arr_n.sort()

for i in range(m):
    left = 0
    right = len(arr_n)-1
    while left<=right:
        mid = (left+right)//2
        if arr_m[i] == arr_n[mid]:
            print(1)
            break
        elif arr_m[i]<arr_n[mid]:
            right = mid-1
        else:
            left = mid+1
    if left>right:
        print(0)

 

이진 탐색을 해서 푸는 문제였는데 이진 탐색이 너무 오랜만이라 까먹고 있었다 ㅎ 

그래서 검색했음 ㅋ ㅋ

이진탐색은 중앙값과 비교하여 중앙값보다 작으면 왼쪽을, 중앙값보다 크면 오른쪽을 택하여 탐색을 계속해 나가는 방식을 사용한다.

left와 right를 사용하고, 중앙값보다 작으면 right를 mid-1로, 중앙값보다 크다면 left를 mid+1로 설정하여 다시 mid를 계산한다.

만약 left값이 right보다 크게 되면 찾는 값이 없다는 의미이므로 0을 출력한다. 

 

이진 탐색의 시간복잡도는 O(longN)으로, 확인하는 데이터 갯수가 절반씩 줄어드는 특징이 퀵 정렬과 동일하다.

탐색해야 하는 데이터의 갯수나 값이 1000만 이상일 경우 O(logN) 수준의 알고리즘을 활용하는 것이 좋다. 

 

 

다른 사람 풀이

ip = input
def main():
    ip()
    n = ip().strip().split(' ')
    ip()
    
    s = set(n)
    r = ''
    for k in input().strip().split(' '):
        r += '1\n' if k in s else '0\n'
    print(r)

if __name__ == "__main__":
    main()

이진 탐색 문제이지만 set를 사용해 푼 코드가 시간이 더 적게 걸리나보다.

 

재귀를 이용한 구현도 가능하다.