백준 10815 : 숫자 카드 (파이썬)

기초적인 이분 탐색 문제였다.

이분 탐색은 리스트가 정렬되어 있을 때 사용할 수 있는 탐색의 한 종류이다.

 

import sys
sys.stdin = open("10815.txt", 'r')
N = int(sys.stdin.readline())
n = [*map(int, sys.stdin.readline().split())]
M = int(sys.stdin.readline())
m = [*map(int, sys.stdin.readline().split())]
n.sort()
for i in m:
    start = 0
    end = N - 1
    mid = (start + end) // 2
    while start <= end:
        if i == n[mid]:
            print(1)
            break
        if i < n[mid]:
            end = mid - 1
        if i > n[mid]:
            start = mid + 1
        mid = (start + end) // 2
    else:
        print(0)

 

※ 제출 후 나중에 리뷰하기 쉽게 한글로 수정하였음

 

import sys
sys.stdin = open("10815.txt", 'r')
카드의수 = int(sys.stdin.readline())
카드들 = [*map(int, sys.stdin.readline().split())]
새로받을카드의수 = int(sys.stdin.readline())
새로받은카드들 = [*map(int, sys.stdin.readline().split())]
카드들.sort()
for 어떤카드 in 새로받은카드들:
    시작 = 0
    끝 = 카드의수 - 1
    중간점 = (시작 + 끝) // 2
    while 시작 <= 끝:
        if 어떤카드 == 카드들[중간점]:
            print(1)
            break
        if 어떤카드 < 카드들[중간점]:
            끝점 = 중간점 - 1
        if 어떤카드 > 카드들[중간점]:
            시작점 = 중간점 + 1
        중간점 = (시작점 + 끝점) // 2
    else:
        print(0)

 

다른 사람의 코드를 보았는데 훨씬 짧은 코드가 있어서 가져와봤다.

해쉬를 이용한 방법인데 누군가 실제로 구현해놓았다.

 

# 이렇게 해도 정답이 나온다.
n = int(input())
n1 = set(map(int,input().split()))
m = int(input())
m1 = list(map(int,input().split()))
k = []
for i in m1:
    if i in n1:
        k.append(1)
    else:
        k.append(0)
print(*k)