백준 10816 숫자카드 2

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

10816번: 숫자 카드 2

 

처음에는 문제를 대수롭지 않게 생각해서 가장 직관적으로 생각한 풀이를 사용했다. 문제에서 주어진 대로 정말 M개의 탐색 카드에서 N개의 숫자카드를 하나 하나 탐색하면서 count를 늘렸다.

 

첫 번째 문제 풀이 (시간 초과)

N = int(input())
cards = list(input().split(' ', N))
M = int(input())
finds = list(input().split(' ', M))
result = []
count = 0
for i in finds:
  for j in cards:
    if i == j:
      count += 1
  result.append(count)
  count = 0
print(*result)

애초에 이분탐색 문제로 분류되어 있어서 시간초과가 뜰거라고 예상은 했다. 해당 알고리즘의 경우 시간 복잡도는 두 개의 반복문으로 인해 O(MN)이다.

 

두 번째 풀이(딕셔너리 사용)

N = int(input())
cards = sorted(list(input().split(' ', N-1)))
M = int(input())
finds = list(input().split(' ', M-1))

#각 cards에 있는 숫자카드가 몇개 있는지 알려주는 dictionary
countmap = dict()

for i in cards: #입력받은 숫자카드들에 대하여
  if i in countmap: #만약 이미 countmap에 있는 수 라면 +1
    countmap[i] += 1
  else:#처음보는 숫자카드이므로 일단 1count를 하고 countmap에 포함한다
    countmap[i] = 1

#### 코드 분기 ####----------------------------------------------

result = []
for j in finds:#입력받은 탐색 숫자카드에 대하여
  if j in countmap:#만약 countmap에 있다면
    result.append(countmap[j])#최종결과에 입력하고
  else:#없으면
    result.append(0)#0출력

print(*result)

해당 코드에서  ####코드 분기####  이전의 코드는 countmap이라는 딕셔너리를 통해 N개의 숫자카드에서 각 숫자카드마다 몇개의 카드가 있는지 맵핑을 해주는 코드이다. 분기까지의 코드에서 countmap이라는 코드 또는 print(countmap)을 작성하면 다음과 같은 결과가 출력이 된다.

입력:
5
1 1 2 3 3
6
1 1 2 4 6 3

print(countmap)

결과:
{'1': 2, '2': 1, '3': 2}

즉, O(N)만큼의 시간 복잡도를 거쳐 각 숫자 카드의 count를 알게 된다.

이를 이후에 M개의 숫자카드가 있는 finds에서 각 숫자 카드의 mapping을 탐색하며 해당 count값만 받아오므로 

코드의 최종 시간 복잡도는 O(M+N)이 될 것이다. 이렇게 풀면 시간초과를 피할 수 있다.