[백준] 1920. 수찾기

백준 1920. 수찾기

1920번: 수 찾기

 

✓ 난이도 : 실버 4

 

✓ 문제풀이 : 이분탐색

조건에서 정수의 수가 100,000으로 주어졌기 때문에 O(NlogN) 정도의 시간복잡도가 요구된다.

이분탐색 알고리즘의 경우 시간복잡도가 O(logN)이므로 해당 조건을 만족할 수 있다.

 

import sys
import time
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))   #주어진 수
m = int(input())
chk = list(map(int, input().split()))   #확인할 수 

arr.sort()

for c in chk:
    s, e = 0, n-1
    ans = 0
    while s <= e:
        mid = (s+e)//2
        if arr[mid] == c:   # 존재 하는 경우
            ans = 1
            break
        elif arr[mid] < c:  # 주어진 수보다 작은 경우
            s = mid+1
        elif arr[mid] > c:  # 주어진 수보다 큰 경우
            e = mid-1
    
    print(ans)

 

 

 

+

이분탐색이 아닌 파이썬의 내장 함수를 사용해보기로 했다.

파이썬의 set의 경우는 존재 여부를 확인하는데 O(1)의 시간복잡도를 가지기 때문에 리스트를 set으로 변경시킨 후 존재 여부를 확인했다.

import sys
input = sys.stdin.readline

n = int(input())
num = list(map(int, input().split()))
m = int(input())
chk = list(map(int, input().split()))
num = set(num)

for x in chk:
    if x in num:
        print(1)
    else:
        print(0)

 

이분탐색의 경우 메모리는 47276KB, 시간은 744ms가 소요됐지만, 

내장함수를 사용한 경우 메모리는 50180KB, 시간은 172ms로 시간이 훨씬 단축된 것을 알 수 있었다.

문제 유형과 조건에 따라 적절한 방법을 사용하면 좋을 것 같다.