99클럽 코테 스터디 13일차 TIL (숫자 카드)

오늘의 학습 키워드:  시간

문제: 숫자 카드

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

 

풀이

시간복잡도를 따져야 하는 문제입니다.

단순하게 숫자 in 숫자 카드 로 풀이 못하는 문제입니다. 상근이가 갖고 있는 숫자카드의 수와 주어지는 정수의 개수가 많아 일반적으로 반복문을 중첩해 돌리는 O(n^2)으로는 시간 초과에 걸리고 맙니다.

따라서 사용가능한 두 가지 방법이 존재합니다. 해시와 이분탐색입니다.

 

1. 해시를 사용한 풀이

해시의 평균 시간복잡도는 O(1)입니다. 따라서 주어진 시간제한에 적합합니다.

import sys

N = int(input())

s_cards = {i:1 for i in list(map(int,sys.stdin.readline().split(" ")))}

M = int(input())

samples = list(map(int,sys.stdin.readline().split(" ")))

answer = []
for s in samples:
    try:
        if s_cards[s]:
            answer.append(1)
    except:
        answer.append(0)

print(*answer)

 

딕셔너리에 키가 존재하면 1 없으면 0으로 결과를 출력합니다.

 

2. 이분탐색을 이용한 풀이

이분탐색의 경우 시간복잡도가 O(log n)입니다.

def bin_search(num, cards):
    left, right = 0, len(cards) - 1
    while left <= right:
        mid = (left + right) // 2
        if cards[mid] == num:
            return 1
        elif cards[mid] < num:
            left = mid + 1
        else:
            right = mid - 1
    return 0

answer = []

for num in samples:
    s = bin_search(num,s_cards)
    answer.append(s)

print(*answer)

 

결과는 이렇습니다.

 

회고

다양한 방식으로 문제를 풀어보는 것도 재미있는 것 같습니다.

내일 학습할 것.

SQL, Python, 독서 음..