[백준 2024/02/07] 1920번 수 찾기 - python ver.

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

1920번: 수 찾기

 

1. 접근 방법

저번에 java로 한번 풀었던 문제이다. 당시에는 binary search를 완벽히 구현하지 못하고 하나씩 실수가 있어서 정답 코드를 약간 참고 했었다.

이번에는 온전히 나의 힘으로 binary search를 구성해보자 하고 풀었다.

 

binary search 란..

binary 즉, 2 구역으로 나누어서 판단하는 것을 반복하는 것이다. 

left, right, mid 변수를 이용한다. -> 기본적으로 List는 정렬 되어 있어야 한다.

 

left ------- mid ------- right

이런식으로 list의 index들을 가리키고, mid 값 (가운데 있는 값)과 찾고자 하는 값을 비교해준다. 찾고자 하는 값이 더 큰 경우에는,

-----------left ---mid---right

으로 left를 mid 자리에 땡겨준다. 이를 반복한다. 

이를 시간 복잡도 상에서 O(n) -> O(logn)의 이점이 있는걸로 알고 있다.

 

코드를 작성하는 과정 중에서 맞닿은 문제로는 다음과 같다.

l = mid + 1
r = mid -1

처음에는 +1 과 -1을 하지 않아서, 무한 loop에 빠지곤 하였다.

이를 해주는 이유는, binary search가 완료 되었을 때,  l <= r 의 조건을 깨뜨리고 밖으로 나가기 위함이다.

그렇지 않다면 l == r인 상태가 반복되기 때문이다.

 

2. 코드

def binary_search(list_sorted, i):
    l = 0
    r = len(list_sorted) - 1

    while l <= r:
        mid = (l + r) // 2
        if i > list_sorted[mid]:
            l = mid + 1
        elif i < list_sorted[mid]:
            r = mid - 1
        else:
            return 1

    return 0

input()
list_orig = list(map(int, input().split()))
input()
list_contrast = list(map(int, input().split()))

list_orig.sort()

for i in list_contrast:
    print(binary_search(list_orig, i))