[Baekjoon] 10816 - 숫자 카드 2 (Python)

문제

[BaekJoon] 10816 숫자 카드 2

1차 시도 (시간 초과)

요소가 m개이고 0인 list cnt를 미리 선언해주고

2중 for문을 돌면서 입력으로 주어진 몇 개 가지고 있는지 맞춰야 할 m_cards와 가지고 있는 카드 num_cards가 같으면 cnt의 그 index를 +1 해주고 출력했다.

결과는 시간초과였다.

import sys
input = sys.stdin.readline

n = int(input())
num_cards = list(map(int, input().split()))
m = int(input())
m_cards = list(map(int, input().split()))

cnt = [0 for _ in range(m)]
for i in range(len(m_cards)):
    for j in range(len(num_cards)):
        if m_cards[i] == num_cards[j]:
            cnt[i] += 1

print(' '.join(cnt))

2차 시도 (시간 초과)

count()를 쓰면 시간을 줄일 수 있지 않을까 생각했고

맞춰야할 카드가 적힌 m_cards를 for문 돌면서

num_cards에서 m_cards의 요소의 갯수를 찾은 다음 cnt의 index와 매핑하여 갯수만큼 더해줬다.

하지만 이것도 시간초과,,

import sys
input = sys.stdin.readline

n = int(input())
num_cards = list(map(int, input().split()))
m = int(input())
m_cards = list(map(int, input().split()))

cnt = [0 for _ in range(m)]

for i in range(len(m_cards)):
    cnt[i] += num_cards.count(m_cards[i])

print(' '.join(cnt))

성공 ✅

Dictionary 이용 - (832 ms / 119756 KB)

이번엔 cnt를 리스트가 아닌 사전(dictionary)로 선언해주었다.

그리고 가지고 있는 카드 num_cards를 for문을 돌면서 가지고 있는 카드 index에는 1을 주고, 이미 있을 때는 +1을 해주어 가지고 있는 카드의 개수를 index에 맞게 cnt에 저장해주었다.

그 다음, 몇 개인지 맞춰야 할 카드 m_cards 를 돌면서 그 카드가 cnt 사전에 있다면 출력해주면 끝이다.

import sys
input = sys.stdin.readline

n = int(input())
num_cards = list(map(int, input().split()))
m = int(input())
m_cards = list(map(int, input().split()))

cnt = {}
for i in num_cards:
    if i in cnt:
        cnt[i] += 1
    else:
        cnt[i] = 1
        
for i in m_cards:
    if i in cnt:
        print(cnt[i], end=' ')
    else:
        print(0, end=' ')

Binary Search(이진 탐색) 이용 - (2460 ms / 115508 KB)

이번에는 이진 탐색을 이용해 풀어보았다.

먼저 binary search 함수를 정의해주고서

num_cards를 정렬해주고, cnt 사전을 선언하고 위 dictionary로 풀었을 때와 같이 작성해주면 정답이다.

import sys
input = sys.stdin.readline

def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2
        if array[mid] == target:
            return cnt.get(target)
        elif array[mid] > target:
            end = mid - 1
        else:
            start = mid + 1
    return 0

n = int(input())
num_cards = sorted(list(map(int, input().split())))
m = int(input())
m_cards = list(map(int, input().split()))

cnt = {}
for i in num_cards:
    if i in cnt:
        cnt[i] += 1
    else:
        cnt[i] = 1

for i in m_cards:
    print(binary_search(num_cards, i, 0, len(num_cards)-1), end=' ')