[알고리즘][Python] 백준(BOJ) 2776 암기왕_파이썬

 

2776 암기왕    www.acmicpc.net/problem/2776

2776번: 암기왕

 

 

 

문제 풀기 전 공부할 것 : 이분 탐색, 정렬

 

 

 

 

 

 

 

풀이 1

<내용>

• 수첩1에 있는 숫자를 set으로 입력받는다.(같은 숫자를 여러 번 봐도 하나만 적혀 있으면 된다.)
  • list로 받으면 시간 초과가 발생한다.
• 수첩2에 있는 숫자를 for문을 통해 반복하면서 수첩1에 있는 숫자인지 확인한다.

 

 

<코드>

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n = int(input())
    nums1 = set(map(int, input().split()))
    m = int(input())
    nums2 = list(map(int, input().split()))
    for num in nums2:
        if num in nums1:
            print(1)
        else:
            print(0)

 

 

 

 

 

 

 

 

 

 

풀이 2

<내용>

• 수첩2에 있는 숫자가 수첩1에 있는 숫자인지 확인하기 위해서 binary_search를 이용한다.

 

<코드>

import sys
input = sys.stdin.readline

def binary_search(s, e, nums1, num):
    while s <= e:
        mid = (s+e) // 2
        
        if nums1[mid] == num:
            return 1
        elif nums1[mid] < num:
            s = mid+1
        else:
            e = mid-1
    return 0

t = int(input())
for _ in range(t):
    n = int(input())
    nums1 = list(map(int, input().split()))
    nums1.sort()
    m = int(input())
    nums2 = list(map(int, input().split()))
    for num in nums2:
        print(binary_search(0, n-1, nums1, num))