[백준_python] 이분 탐색 - 수 찾기 || 1920

www.acmicpc.net/problem/1920

1920번: 수 찾기

이분 탐색

• left와 right를 정하고 중간값(mid)와 찾을 값을 비교해준다.!
• mid보다 찾을 값이 크다면 left값을 mid보다 1 큰 값으로 올려주기 (범위 → : 값이 큰 쪽으로)
• mid보다 찾을 값이 작다면 right값을 mid보다 1 작은 값으로 내려주기 ( ← 범위 : 값이 작은 쪽으로)
• 얼마동안? left <= right일 동안

추가로 시간 복잡도 얘기를 해보자면,

• list의 시간 복잡도는 O(N)
• 이분 탐색의 시간 복잡도는 O(logN)
• Set과 Dictionary의 in연산 시간 복잡도는 O(1)

이라고 한다.!

---

#수 찾기
#! 시간복잡도 O(N)
#? 시간초과!
n = int(input())
a = list(map(int, input().split(' ')))
m = int(input())
b = list(map(int, input().split(' ')))
result = []
for i in b:
    if i in a:
        result.append(1)
    else:
        result.append(0)
print(*result, sep = "\n")

시간 초과가 떠서 뭐지뭐지 했는데 문제 밑에 알고리즘에 이분 탐색이라고 적혀있었다.!
원하는 값을 해당 리스트에서 찾으려고 비교하는 부분은 이분탐색으로 시간을 줄일 수 있었다
 
따라서, 이분 탐색을 이용하여

#수 찾기_2
#! 시간 복잡도 O(logN)
#? 이분 탐색
n = int(input())
a = list(map(int, input().split(' ')))
a.sort()
m = int(input())
b = list(map(int, input().split(' ')))
result = []

for i in b:
    left = 0
    right = n - 1
    while(left<=right):
        mid = (left+right)//2
        if i < a[mid]:
            right = mid -1
        elif i > a[mid]:
            left = mid + 1
        elif i == a[mid]:
            result.append(1)
            break
    if left > right:
        result.append(0)
print(*result, sep = "\n")

전에 이분 탐색을 이용하는 문제를 풀었어서 이번에 잘 해결할 수 있겠지? 했었는데...
까먹기도 하고,, 어떻게 하는 지는 알겠는데도 결과값이 잘 나오지 않았었다.
이전에 풀었었던 코드를 보면서 다시 따라 해보았고, 리스트를 sort해주어야 하는 부분 또한 잊고 있었다!
 
다음 이분 탐색 관련 문제가 또 나오더라도 그 때엔 틀리지 않도록 잘 익혀두어야 겠다!
 

#수 찾기_3
#! set, dictionary의 시간 복잡도는 O(1)
n = int(input())
a = set(map(int, input().split(' ')))
m = int(input())
b = list(map(int, input().split(' ')))
result = []
for i in b:
    if i in a:
        print(1, sep = "\n")
    else:
        print(0, sep = "\n")

set 자료형의 in연산을 통한 시간 복잡도는 O(1)이기 때문에 가장 시간이 짧게 걸린다.!
실제로 이분탐색은 740ms인데 이 코드는 188ms가 나왔다.
 
 
참고한 사이트!)
chancoding.tistory.com/44

[Python] 백준 1920번 수 찾기 - 두가지 풀이:이분탐색과 자료형