[Python] 백준 10816번 숫자 카드 2 - 정렬, 딕셔너리

백준 홈페이지 문제와 개인적인 풀이를 작성한 글입니다.

 

백준 10816번 : 숫자 카드 2

10816번: 숫자 카드 2

 

---

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

 

출력 

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

 

예제 입력 1	예제 출력 1
10 6 3 10 10 10 -10 -10 7 3 8 10 9 -5 2 3 4 5 -10	3 0 0 1 2 0 0 2

 

내 코드 - 실패 (시간 초과)

# 10816번 숫자 카드2

import sys;

input = sys.stdin.readline;

n = int(input());
array = list(map(int, input().split()));

m = int(input());
array2 = list(map(int, input().split()));

data = []
for i in range(m):
    count = 0;
    for j in range(n):
        if array2[i] == array[j]:
            count += 1;
    data.append(count);
print(*data)

 

다른 사람 코드 - 성공

# 숫자 카드 2 10816번

import sys
input = sys.stdin.readline

N = int(input());
cards = list(map(int, input().split()));

M = int(input())
numbers = list(map(int,input().split()));

count = {}
for card in cards:
    if card in count:
        count[card] += 1;
    else:
        count[card] = 1;

for target in numbers:
    result = count.get(target);
    if result == None:
        print(0, end=" ");
    else:
        print(result, end=" ");

 

풀이 후 느낀 점

필자는 문제를 풀 때, for 문을 많이 사용하는 것을 지양하고 있습니다.
이중 포문 까지는 쓰지만, 삼중 포문까지는 문제 해결할 때 잘 사용하지 않는 장점이자 단점? 이 있습니다.

 

굉장히 간단한 문제라고 생각을 했고, 시간초과를 걸리는 것을 봤을 때 이분탐색을 사용하면 되겠다고 생각했습니다. 

(이분탐색을 풀면 다른 분들은 통과가 나왔지만, 필자는 시간초과가 계속 나와서 실패했습니다. ^^)

 

결국 실패하고 다른 분들 풀이를 보니 간단하게 딕셔너리를 사용해서 푸는 것을 보고, 참고하여 풀었습니다.

참고하시고, 차후 기초 다지기에 좋은 문제라고 생각합니다.