[Python][백준 BOJ ] 10815. 숫자 카드 : 시간 초과 해결, 딕셔너리 vs 리스트, 이분 탐색

접근 방식

입력으로 주어진 M개의 수와 상근이가 가지고 있는 숫자 카드 중 일치하는 값이 있는지 순차적으로 확인한다.

 ❌ Solution 1 - 시간 초과

import sys
n = int(sys.stdin.readline())
cards = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
num = list(map(int, sys.stdin.readline().split()))

for i in num:
    if i in cards:
        print(1, end=" ")
    else:
        print(0, end=" ")

이 코드 내에서 시간이 오래 걸릴만한 부분은 if i in cards라고 생각했다.

찾아보니 리스트는 요소 하나하나를 조회할 때 최악의 경우 O(n)의 시간 복잡도를 가진다하여 더 빠른 자료형을 사용해야겠다고 생각했다.

✅ Solution 2 - dictionary, set 이용

딕셔너리와 세트는 검색, 삽입 및 삭제 작업에 대해 O(1)의 시간 복잡도를 갖는다. (조회, 삽입, 삭제에 대해 내부적으로 동일한 해싱 메커니즘 사용)

리스트는 배열로 구현되며 목록 내에서 검색하면 목록의 각 요소를 반복하여 일치하는 항목을 찾기 때문에 최악의 경우 시간 복잡도는 O(n)이다.

따라서 검색 문제를 해결할 때, (특히 요소 수가 많고 조회 효율성이 중요한 경우) 딕셔너리와 세트를 사용하면 리스트보다 더 빠르게 해결할 수 있다.

 

딕셔너리는 키-값 쌍을 저장하는 반면, 세트은 고유한 요소를 저장한다.

따라서 키-값 쌍이 있는 경우 딕셔너리를 선택하고, 고유한 요소만 저장하고 값을 연결할 필요가 없는 경우에는 집합을 사용하자.

딕셔너리는 키-값 쌍을 저장하므로 집합에 비해 메모리 오버헤드가 약간 더 높을 수 있어 키-값 쌍이 필요하지 않다면 세트를 사용하는 것이 적절하다.

세트

import sys
n = int(sys.stdin.readline())
cards = set(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
num = list(map(int, sys.stdin.readline().split()))

for i in num:
    if i in cards:
        print(1, end=" ")
    else:
        print(0, end=" ")

변수 cards는 상근이가 가진 카드에 적힌 숫자(중복 X)만을 저장하므로 set형을 이용하였다.

딕셔너리

import sys
n = int(sys.stdin.readline())
cards = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
num = list(map(int, sys.stdin.readline().split()))

card_dict = {i: 0 for i in cards}    # 딕셔너리 컴프리헨션

for i in num:
    if i in card_dict:
        print(1, end=" ")
    else:
        print(0, end=" ")

cards를 딕셔너리형으로 이용하려면 카드에 적힌 숫자를 키로 두고, 값은 필요 없으니 아무 숫자로 세팅해준다. (코드 내에선 0으로 세팅)

 

---

✅ Solution 3 - 이분 탐색

import sys
n = int(sys.stdin.readline())
cards = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
num = list(map(int, sys.stdin.readline().split()))

def binary_search(arr, target):
    start = 0
    end = len(arr) - 1

    while(start <= end):
        mid = (start + end) // 2

        if arr[mid] == target:
            return True
        elif arr[mid] > target:
            end = mid - 1
        else:
            start = mid + 1

cards.sort()
for i in num:
    if binary_search(cards, i): # True
        print(1, end = " ")
    else:
        print(0, end = " ")

사실 이 문제는 이분 탐색을 연습하려고 푼 문제였다.

다만 cards와 num중 어느 것을 binary_search()의 arr로 설정해야할지 헷갈려서 처음 풀이에서 이분 탐색을 사용하지 않았다.

num이 cards 내에 있는지 확인해야 하니 binary_search()의 arr에는 cards가 들어가면 된다.

 

이분 탐색을 이용하면 num과 같은 값이 cards에 있는지 확인할 때 모든 요소를 순차적으로 탐색하지 않아도 된다.

cards의 중간값(mid)부터 num과 비교해 num > mid라면 범위를 절반으로 줄여 mid의 오른쪽에서만 num을 탐색할 수 있기 때문이다.

💭What I Learned

1. 존재 여부를 탐색할 때 리스트(O(n))보다 딕셔너리(O(1))가 더 빠르다.
2. 이분 탐색을 할 때 무엇을 탐색 대상으로 할 지 잘 생각해보자.
3. 이 문제에서는 사용하지 않았지만 bisect()를 사용해 이분 탐색을 할 수도 있다.

---

https://www.acmicpc.net/problem/10815

10815번: 숫자 카드