[백준/Python] 1920 : 수 찾기

 

<첫 번째 시도>

N = int(input())
Alst = list(map(int, input().split()))
M = int(input())
Blst = list(map(int, input().split()))
for i in range(len(Blst)):
    if Blst[i] in Alst: print(1)
    else: print(0)

 

일단 정렬 문제라서 위와 같이 작성하면 안될 것 같았지만, 혹시나해서 테스트해봤더니 역시나 시간 초과 오류로 틀렸다.

적절한 정렬 알고리즘을 사용해야 시간을 줄일 수 있는 것 같았음

 

일단 찾아보니 리스트에서 in 연산자를 사용하는 것을 리스트에서 특정 값을 찾을 때 선형 탐색을 하며, 시간 복잡도는 O(N)으로서 위 코드를 실행할 때의 전체 시간 복잡도는 O(M*N)이다.

 

문제에서 주어지는 입력의 크기가 커지면 해당 방식은 매우 비효율적이게 되는데, 예로 N과 M이 각각 100,000일 경우 O(M*N)은 최대 10,000,000,000이 되므로 시간 초과가 발생하게 된다.

 

따라서 리스트 대신 이진 탐색을 사용하면 시간 복잡도를 O(NlogN)으로 줄일 수 있다기에, 이를 이용하여 Alst를 정렬하고, Blst의 각 원소에 대해 이진 탐색을 수행하면 효율적으로 탐색할 수 있을 것이다!

 

이는 파이썬의 bisect 모듈을 사용하면 이진 탐색을 수행할 수 있지만, 일단 하드코딩으로 직접 구현해보자.

 

 

<최종 정답 코드>

N = int(input())
Alst = sorted(map(int, input().split())) # Alst 배열을 미리 정렬 
M = int(input())
Blst = list(map(int, input().split()))

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left+right) // 2
        if arr[mid] == target:
            return True
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return False

# Blst 각 원소에 대해 이진 탐색 수행
for b in Blst:
    if binary_search(Alst, b):print(1)
    else: print(0)

 

• 입력받은 리스트 Alst를 먼저 sorted로 정렬한다. (이진 탐색은 정렬된 배열에서만 동작하기 때문) 이렇게 미리 정렬함으로써 반복문에서 매번 찾거나 매번 정렬하는 등의 비효율적인 일을 줄일 수 있게 된다!
• binary_search 이진 탐색 함수
  • left: 배열의 왼쪽 끝 / right: 배열의 오른쪽 끝  / mid는 배열의 중간 인덱스로서 중간값을 확인함
  • 만약 mid 값이 target과 같으면 True를 반환하고, 그렇지 않으면 값을 기준으로 왼쪽이나 오른쪽 절반만 다시 탐색
  • 이를 left > right 일 때까지 반복