[Python] 2776 - 암기왕

1. 문제 정의

수첩 1, 수첩 2가 주어진다. 주어진 각 수첩의 내용이 일치한지를 검사하는 프로그램을 작성하는 것이 이번 문제의 목표이다.

 

2. 풀이 방식

문제를 해결하기 위해 이진 탐색(Binary Search)를 사용하였다. 

이진 탐색을 진행하기 위한 search() 함수를 정의하였고, 수첩 1, 수첩 2의 내용을 담기 위한 리스트를 생성하여 리스트 내부를 탐색하는 프로그램을 구현하도록 하였다.

 

# 2776 암기왕

import sys

input = sys.stdin.readline
T = int(input())

# 탐색 메소드
def search(num, li, e):
    start, end = 0, e-1 # 시작값, 끝값 설정정
    
    while (start <= end):
        mid = (start + end) // 2 # 이진 탐색을 위한 중앙값값
        if (num == li[mid]): # 일치하는 경우
            print(1)
            break
        else: # 일치하지 않은 경우, case에 따라 시작값, 끝값을 조정정
            if (num > li[mid]):
                start = mid + 1
            else:
                end = mid - 1
        
        # 시작값 또는 끝값이 중앙값과 같다 -> 탐색을 끝까지 진행하였다.
        if (start == mid) or (end == mid):
            print(0)
            break

for _ in range(T):
    # 정답 리스트
    n = int(input())
    n_list = list(map(int, input().split()))

    # 답안지 리스트
    m = int(input())
    m_list = list(map(int, input().split()))

    n_list.sort()

    for ix in m_list: # 답안지 리스트 탐색
        search(ix, n_list, n)

 

3. 후기

오늘 첫 개강한 항해99의 99클럽 코딩테스트 1일차 문제였다. 중급 난이도 문제여서 그런지 내가 평소에 풀던 문제들과 비슷한 느낌이라 큰 어려움 없이 문제를 해결하였다.

이진 탐색을 활용하여 해결하는 문제였는데, 이진 탐색의 개념에 대해 좀 더 알아보는 시간이 되었다.