백준 2776번 파이썬 문제 풀이

문제

연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, 연종이 하루 동안 본 정수들을 모두 ‘수첩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에 적어둔 값은 총 100만개고, 수첩 2에  적어둔 값 역시 총 100만개다. 이를 하나하나 비교할 경우 시간 복잡도는 O(N^2)이 되어, 절대로 풀 수 없다. 따라서 완전탐색이 아닌 이진탐색으로 O(nlogn) 수준으로 시간복잡도를 줄여야 가능하다. 

문제는 다음 로직으로 접근했다.

1. 수첩1의 값을 오름차순 순으로 정렬한다
2. 수첩 2의 값을 하나씩 수첩 1에서 이진탐색한다.
3. 이진탐색 시, 값이 존재할 경우 Print(1)을 했고, 존재하지 않을 경우 Print(0)을 했다.

이진 탐색의 세부 논리는 다음과 같다.

1. 중심 좌표를 설정한다.
2. 중심 좌표에 있는 값과 찾고자 하는 값의 대소 비교를 진행한다.
3. 대소 비교 진행 후, 구간을 재설정한다
   3-1. 만약 값이 같을 경우, 1을 출력하고 탐색 종료
   3-2. 현재 위치의 값이 찾고자 하는 값보다 작을 경우, 더 큰 구간을 봐야한다. (L = M + 1)
   3-3. 현재 위치의 값이 찾고자 하는 값보다 클 경우, 더 작은 구간을 봐야한다. (R = M - 1 )
4. 1~3번 과정을 L <= R 일 때 까지 반복한다. 왜냐하면, L == R 일 때, 원하는 값이 나올 수 있기 때문이다.

위의 과정을 코드로 작성하면 아래와 같다.

import sys


#이진탐색
def sol(find_list, num) :
    l = 0
    r = len(find_list) - 1

    while l <= r :
        mid = (l + r + 1) // 2
        if find_list[mid] < num :
            l = mid + 1
        elif find_list[mid] > num :
            r = mid - 1
        elif find_list[mid] == num :
            print(1)
            return
    else : print(0)



for _____ in range(int(sys.stdin.readline().rstrip())) :
    #변수 입력
    n = int(sys.stdin.readline().rstrip())
    find_list = list(map(int,sys.stdin.readline().split()))
    m = int(sys.stdin.readline().rstrip())
    note = list(map(int,sys.stdin.readline().split()))
    
    #수첩1번 오름차순 정렬
    find_list = sorted(find_list)
    
    #수첩2번 숫자 각각에 대해서 수첩 1에서 이진탐색 진행
    for num in note :
        sol(find_list, num)