[백준] 10815: 숫자 카드 - 파이썬[python]

다인·2024년 9월 13일

백준

목록 보기

60/112

당연히 시간 초과가 안 나게 풀어보라고 낸 문제 같았다. 그런데 도저히 떠올리지 못했고... 다른 코드들을 참고했다. 이진 탐색으로 푸는 방법과 시간초과 방법과 똑같이 풀지만 N개의 카드들을 set 혹은 dictionary로 저장하는 방법이 있다.

1. set 이용

import sys

N = int(input())
cards = set(map(int, sys.stdin.readline().split()))
M = int(input())

finds = list(map(int, sys.stdin.readline().split()))
for i in finds:
    if i in cards:
        print(1, end=' ')
    else:
        print(0, end=' ')

이게 가능한 이유는 해싱값을 인덱스로 사용해서 데이터를 저장하는 해시 테이블 구조이기 때문이다.
따라서 i in cards를 수행했을 때 시간복잡도는 O(1)이 된다. 리스트는 O(n)이다.
remove도 마찬가지로 set을 썼을 때 O(1)의 시간복잡도가 나온다.
참고

2. dictionary 이용

import sys

N = int(input())
cards = list(map(int, sys.stdin.readline().split()))
M = int(input())
finds = list(map(int, sys.stdin.readline().split()))

dic = {}
for i in cards:
    dic[i] = 1

for i in finds:
    if i in dic:
        print(1, end=' ')
    else:
         print(0, end=' ')

1의 코드를 딕셔너릴 이용해 다시 작성한 코드이다.
N개만큼 입력받은 애들을 딕셔너리의 key 값으로 사용하고 value 값은 1로 해주었다(아무거나 상관없음)
M개만큼 입력받은 애들을 하나씩 살펴보며 딕셔너리의 key 값으로 존재하면 1을, 아니면 0을 출력한다.

조금 더 원초적인 방법

import sys

N = int(input())
cards = list(map(int, sys.stdin.readline().split()))
M = int(input())
finds = list(map(int, sys.stdin.readline().split()))

dic = {}
for i in finds:
    dic[i] = 0

for i in cards:
    if i in dic:
        dic[i] = 1

for i in dic:
        print(dic[i], end=' ')

진짜 기본적(?)인 방법이다.
찾고자 하는 애들을 key 값으로 하고 value를 0으로 초기화한다.
N개만큼 입력받은 애들은 value값 을 1로 바꾸어준다.(존재한다는 뜻)
그리고 딕셔너리의 value 값을 출력한다.
N의 개수가 크지 않았다면 가능한 입력 개수만큼 리스트를 선언했을 수도 있다. 그럴 때 불필요한 메모리를 낭비하지 않기 위해 dictionary를 사용할 수도 았겠다.

3. 이진 탐색

import sys

N = int(input())
cards = list(map(int, sys.stdin.readline().split()))
M = int(input())
finds = list(map(int, sys.stdin.readline().split()))

cards.sort()

def binary_search(target):
    low, high = 0, N-1

    while low <= high:
        mid = (low + high) // 2
        if target == cards[mid]:
            return 1
        elif target > cards[mid]:
            low = mid + 1
        else:
            high = mid - 1
    return 0

for i in finds:
    print(binary_search(i), end=' ')