[홀로 하는 코딩 공부] 암기왕 (Python)

백준

사용 언어: Python

문제 링크: https://www.acmicpc.net/problem/2776

2776번: 암기왕

 

*** 본 문제를 푸는 과정을 공유하려 한다.

---

▶ 보자마자 완전 탐색으로 하기에는 정수의 개수가 너무 크다는 조건이 걸려서 이분탐색으로 풀어야 겠다고 생각했다.

 

▶ 수첩2를 기준으로 출력하는 것이기떄문에 수첩2 내 값의 위치를 바꾸면 안된다. 하지만 수첩1의 경우에는 수첩1 내에 값이 존재하는지 여부만 출력하는 것이지 인덱스를 출력하는 것이 아니기 때문에 수첩1 내 값의 위치를 바꿔도 된다. 그래서 수첩1은 sorted함수를 이용하여 오름차순 해준다. 그러고 수첩2의 값을 하나씩 이분탐색으로 수첩1을 탐색해나가면서 존재하는지 여부만 flag 변수를 통해 확인해주면 되는 단순 이분탐색 문제였다.

▶ 위의 내용처럼 코드를 작성하면 아래와 같고 통과다!

import sys
input = sys.stdin.readline

T = int(input())

def binary_search(arr, tgt):
    left, right = 0, len(arr)-1
    flag = False
    while left <= right:
        mid = (left+right) // 2

        if arr[mid] < tgt:
            left = mid + 1
        elif arr[mid] > tgt:
            right = mid-1
        else:
            flag = True
            break
    return flag


for _ in range(T):
    N = int(input())
    N_list = sorted(list(map(int, input().split())))
    M = int(input())
    M_list = list(map(int, input().split()))

    for M_value in M_list:
        if binary_search(N_list, M_value):
            print('1')
        else:
            print('0')

 

---

>> 위 내용은 필자가 코딩테스트 문제를 푼 코드입니다.

>> 부족한 점이 많을 수 있기에 잘못된 내용이나 궁금한 사항이 있으면 댓글 달아주시기 바랍니다.

>> 긴 글 읽어주셔서 감사합니다.