Baekjoon 문제 풀기 (1920번 : 수 찾기) Python

1920번 : 수 찾기

1. 문제읽기

---

이진 탐색 알고리즘 문제

문제는 이해하기 쉬웠다.
첫번째 n개의 숫자 집합 안에 m개의 숫자 하나하나씩 비교하여 있으면 1 없으면 0 을 출력하면 된다.

2. 제출 코드

---

당연히 처음에는 for문과 in을 사용하여 코드를 짰지만 리스트에서 in은 시간복잡도 O(n)이 걸리므로 총 시간복잡도는 $O(n^2)$ 이기 때문에 입력값이 10만개인 이 문제는 시간초과 각이였다.
따라서 O(nlogn)까지 줄일 수 있는 이진탐색을 이용하여 문제를 풀었다.

이진탐색은 정렬이 되어있는 리스트만 가능하기 때문에 정렬해주고, start가 end보다 크면 반복문을 종료한다.
조건문을 계속 elif else 이렇게 쓰면서 헤멨었는데, 클 때와 작을 때만 if문으로 구분하고 맞는 경우를 else로, 그리고 종료하는 부분을 while문에 쓰던지 if문으로 따로 써주면 해결된다.
많이 풀어서 익숙해지는 방법밖에는 없는 것 같다.
요 며칠 문제를 계속 틀려서 우울했는데, 맞아서 기분이 좀 나아졌다.

n = int(input())

arr = list(map(int, input().split()))
arr.sort()
# arr = [1, 2, 3, 4, 5]
m = int(input())

target = list(map(int, input().split()))
start = 0
end = 0
for i in target:
    start = 0
    end = len(arr) - 1
    while 1:
        mid = (start + end)//2
        if i < arr[mid]:
            end = mid-1
        elif i > arr[mid]:
            start = mid+1
        else:
            print(1)
            break
        if start > end:
            print(0)
            break

3. 공부할 것

---

이진탐색 말고 set 자료형을 이용하여 푸는 방법이 있다.
list는 in을 사용하면 O(n)의 시간 복잡도를 가지는데, set의 in은 O(1)이다.
set의 중복을 허용하지 않는 특성과 순서가 없다는 특징 때문이다.

그러나 m의 숫자들도 set으로 받게 되면, set은 숫자를 받을 때 정렬되어 입력시키기 때문에 입력 순서가 바뀌기 때문에 답도 달라진다.

채점을 돌려보니 기존 이진탐색 코드보다 약 1/4만큼 시간이 줄어들었다.
값이 포함되어있는지 찾을 때, 찾는 숫자의 집합이 중복되지 않은 집합이라면 set을 사용하는 것을 고려해봐야겠다.

n = int(input())
arr = set(map(int, input().split()))
m = int(input())
target = list(map(int, input().split()))

for i in target:
    if i in arr:
        print(1)
    else:
        print(0)