[백준 2776] 암기왕

문제 출처 : https://www.acmicpc.net/problem/2776

 

수첩 1에 있는 정수가 수첩 2에 있으면 1을, 없으면 0을 출력하는 문제 입니다.

문제 이해하기

수첩 1의 순서가 중요한 것이 아니기 때문에 수첩 1을 정렬한 다음, 수첩 2의 숫자로 이분탐색을 하여 결과를 출력하면 됩니다.

이 방법보다 더 쉬운 방법은 수첩 1을 set 자료구조로 저장하여 찾는 것입니다. 간단한 문제이기 때문에 이분 탐색, set 두 가지 방법 모두 해보겠습니다.

코드작성

이분 탐색의 입력부터 알아보겠습니다.

입력 받기

mii = lambda : map(int, input().split())
T = int(input())

for _ in range(T):
    N = int(input())
    arr = list(mii())
    arr.sort()
    M = int(input())
    note = list(mii())

    for n in note:
        print(binary_search(n))   

먼저 테스트 케이스의 개수 T를 입력 받습니다. 다음으로 T개의 테스트에 맞게 입력을 받습니다.

N은 수첩 1에 있는 정수의 개수 입니다. arr은 수첩 1의 내용 입니다. arr은 이분 탐색을 하기 위해서 정렬을 수행 합니다.

다음으로 수첩 2의 정수의 개수 M을 입력 받습니다. 다음으로 수첩 2에 있는 숫자를 note에 입력 받습니다.

반복문을 수행하면서 노트의 숫자들을 이분 탐색을 통해 검색합니다. 리턴받은 숫자를 출력해주면 됩니다.

이분 탐색

def binary_search(x):
    left = 0
    right = len(arr) - 1

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] == x:
            return 1
        elif arr[mid] < x:
            left = mid + 1
        else:
            right = mid - 1
    
    return 0

이분 탐색 코드 입니다. arr에 있는 정수들을 검색하여 해당 정수가 존재하면 1을 리턴하고 아니라면 left나 right 값을 변경하면서 이분 탐색을 계속 합니다. 최종적으로 정수가 존재하지 않는다면 0을 리턴하게 됩니다.

set 입력

다음으로 set으로 문제를 해결하는 코드를 확인해 보겠습니다.

for _ in range(T):
    N = int(input())
    arr = set(mii())

    M = int(input())
    note = list(mii())

    for n in note:
        print(search(n))

입력 받는 부분이 조금 틀려졌습니다. 먼저 arr이 list가 아닌 set으로 입력 받았습니다. 그리고 set에는 순서가 없기 때문에 sort를 하지 않습니다. 그 외에는 이분 탐색과 똑같은 코드 입니다.

set 탐색

set은 해시를 사용하기 때문에 정수가 존재하는지 빠르게 찾을 수 있습니다.

def search(x):
    if x in arr:
        return 1
    else:    
        return 0

간단하게 in을 통해 있으면 1을, 없으면 0을 리턴하도록 하면 됩니다.

공부를 위해서라면 set보다는 이분 탐색을 사용하기를 바랍니다. 하지만 시험이라면 빠르게 문제를 해결하고 다른 문제를 풀 수 있도록 set을 사용하는 것이 좋습니다.

전체 코드

이분 탐색과 set 사용에 대한 전체 코드 입니다.

이분 탐색

mii = lambda : map(int, input().split())
T = int(input())

def binary_search(x):
    left = 0
    right = len(arr) - 1

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] == x:
            return 1
        elif arr[mid] < x:
            left = mid + 1
        else:
            right = mid - 1
    
    return 0

for _ in range(T):
    N = int(input())
    arr = list(mii())
    arr.sort()
    M = int(input())
    note = list(mii())

    for n in note:
        print(binary_search(n))

set 사용

mii = lambda : map(int, input().split())
T = int(input())

def search(x):
    if x in arr:
        return 1
    else:    
        return 0

for _ in range(T):
    N = int(input())
    arr = set(mii())

    M = int(input())
    note = list(mii())

    for n in note:
        print(search(n))