백준 10815 - 파이썬

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

10815번: 숫자 카드

문제 풀이

이번 문제는 서로 비교하여 카드가 존재하는지만 확인하면 되는 문제이기 때문에 금방 구현 과정으로 옮겼다. 다만 어떤 알고리즘을 활용하여 탐색을 할까 하다가 일단은 이중반복문을 사용하여 탐색을 하였다.

 

import sys
input = sys.stdin.readline

n = int(input())
myCard = list(map(int,input().split()))

m = int(input())
card = list(map(int,input().split()))

result = [0] * m
for i in range(m):
    cnt = 0
    for j in range(n):
        if myCard[j] == card[i]:
            cnt += 1
    result[i] = cnt
            

for num in result:
    print(num, end=" ")

 

하지만 이 코드는 시간 초과가 났다. 그래서 다른 방법을 찾아봤는데 이진탐색을 활용했다.

 

import sys

n = int(sys.stdin.readline())
cards = sorted(list(map(int, sys.stdin.readline().split())))
m = int(sys.stdin.readline())
checks = list(map(int, sys.stdin.readline().split()))

for check in checks:
    low, high = 0, n-1 
    exist = False
    while low <= high:
        mid = (low + high) // 2
        if cards[mid] > check:
            high = mid - 1 
        elif cards[mid] < check:  
            low = mid + 1 
        else:
            exist = True
            break
    print(1 if exist else 0, end=' ')

 

이진 탐색의 경우 시간복잡도가 O(logN)이기 때문에 무난하게 통과됐다. 다음 코드는 딕셔너리를 활용한 코드이다. 

 

import sys
from collections import deque
input = sys.stdin.readline

n = int(input())
cards = list(map(int,input().split()))
m = int(input())
checks = list(map(int,input().split()))

cardDict = {}
for i in range(n):
    cardDict[cards[i]] = 0

for i in range(m):
    if checks[i] in cardDict:
        print(1, end=" ")
    else:
        print(0, end=" ")

 

딕셔너리를 활용하여 푸는 문제는 구글링을 통해 다른 사람들의 풀이를 참고했다. 이 코드를 보다 보면 굳이 딕셔너리를 사용하지 않아도 될 듯하다. 그래서 딕셔너리를 제거하고 제출을 해 봤는데 시간 초과가 났다. 딕셔너리와 리스트의 시간 복잡도가 차이가 있나 싶어 구글링을 해 보니 차이가 있었다.

 

리스트

출처: https://ok-lab.tistory.com/232

 

딕셔너리

출처: https://ok-lab.tistory.com/232

리스트의 경우 어떤 연산인지에 따라 시간복잡도가 달라지지만, 딕셔너리의 경우 내부적으로 해시테이블로 구현이 되어 있기 때문에 모든 연산에서 시간 복잡도가 O(1)이다. 이런 차이 때문에 연산 속도에서 차이가 났던 것이다.

 

느낀점

이번 문제에서는 코드를 작성하는 거 외에도 리스트와 딕셔너리의 시간복잡도 차이를 알 수 있었던 문제였다. 또한 이진탐색도 오랜만에 사용하여 가물가물했는데 다시 한번 기억을 상기시킬 수 있었던 문제였다.