[BOJ] #2776_암기왕(Python3, 파이썬)

본 게시글은 백준 저지 알고리즘 문제를 '파이썬, Python3' 언어로 풀이한 내용을 주관적으로 정리하였으며, 내용과 관련된 코드리뷰 및 피드백 환영합니다.

티어

Silver IV

문제

연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 
그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, 연종이 하루 동안 본 정수들을 모두 ‘수첩1’에 적어 놓았다. 
그것을 바탕으로 그가 진짜 암기왕인지 알아보기 위해, 동규는 연종에게 M개의 질문을 던졌다. 질문의 내용은 “X라는 정수를 
오늘 본 적이 있는가?” 이다. 연종은 막힘없이 모두 대답을 했고, 동규는 연종이 봤다고 주장하는 수 들을 ‘수첩2’에 적어 두었다.
집에 돌아온 동규는 답이 맞는지 확인하려 하지만, 연종을 따라다니느라 너무 힘들어서 여러분에게 도움을 요청했다. 
동규를 도와주기 위해 ‘수첩2’에 적혀있는 순서대로, 각각의 수에 대하여, ‘수첩1’에 있으면 1을, 없으면 0을 출력하는 프로그램을 작성해보자.

입력

첫째 줄에 테스트케이스의 개수 T가 들어온다. 다음 줄에는 ‘수첩 1’에 적어 놓은 정수의 개수 N(1 ≤ N ≤ 1,000,000)이 입력으로 
들어온다.
그 다음 줄에  ‘수첩 1’에 적혀 있는 정수들이 N개 들어온다. 그 다음 줄에는 ‘수첩 2’에 적어 놓은 정수의 개수 M(1 ≤ M ≤ 1,000,000) 
이 주어지고, 다음 줄에 ‘수첩 2’에 적어 놓은 정수들이 입력으로 M개 들어온다. 모든 정수들의 범위는 int 로 한다.

출력

‘수첩2’에 적혀있는 M개의 숫자 순서대로, ‘수첩1’에 있으면 1을, 없으면 0을 출력한다.

예제 입력 및 출력 1

1
5
4 1 5 2 3
5
1 3 7 9 5

1
1
0
0
1

---

풀이

import sys
input = sys.stdin.readline

def binary_search(target, array, start, end):
    if start > end:
        return None

    mid = (start + end) // 2

    if array[mid] == target:
        return mid
    elif array[mid] > target: 
        return binary_search(target, array, start, mid-1)
    else:
        return binary_search(target, array, mid+1, end)

for _ in range(int(input())):
    N = int(input())
    note_1 = list(map(int, input().split()))
    M = int(input())
    note_2 = list(map(int, input().split()))

    note_1.sort()
    for note in note_2: # 1
        result = binary_search(note, note_1, 0, N - 1) 
        if result == None:
            print(0)
        else:
            print(1)

처음에 for _ in 리스트: 구문으로 풀어서 시간 초과가 떴다. 아무래도 테스트케이스를 받을 뿐더러 for문을 계속 사용하니 시간 복잡도가 커져서 그런 것 같다. 이 문제는 이분 탐색으로 풀어야 하는 문제인 것 같았다.

이분탐색은 target, array, start, mid, end 이렇게만 있으면 풀 수 있다. 0~(N-1)까지 검사를 하고, 리스트에서 하나씩 변수를 꺼내서 절반씩 검사하는 개념이다. mid = (start + end) // 2 mid를 기준으로 두고, mid와 target이 일치할 때까지 재귀한다. 리스트의 중심을 중심으로 왼쪽이면 start값은 그대로 start, end값은 end-1로, 반대로 오른쪽이면 start값이 mid+1이 되고, end값은 그대로 end로 가져간다. 

여기서 주의할 점은 이분 탐색에서 쓰이는 배열(array), 즉 리스트가 반드시 정렬되어 있어야한다는 점이다. 이 점을 까먹고 계속 왜 안되지 하면서 애를 먹었던 것 같다. 다음부터는 조심해야겠다.