[Python] 백준 10816번 문제풀이 - 숫자카드2

문제 링크

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

아이디어

이 문제는 후보군에 나온 카드를 상근이가 몇 장 가지고 있는지 출력하는 문제입니다.

 

처음에 알고리즘 분류를 봤을 때 이분 탐색이 있어서 이분 탐색으로 해봐야겠다고 생각하고

제가 익혔던 이진 탐색 코드를 사용해서 자신 있게 mid를 찾고 return 하려고 하는데, 같은 값을 여러 개 찾아서 출력해야 했습니다.

그래서 같은 값을 찾으면 양 옆으로 뻗어가며 상근이의 카드에서 일치하는게 몇 개 있는지 찾으려 했는데, 구현이 저에게는 어려워서 포기하고 다른 사람들의 풀이를 보았습니다.

 

저랑 같은 생각을 하신 분이 있었는데 그 분은 구현했지만 시간복잡도를 충족을 못해서 다른 풀이를 찾으셨습니다.

그래서 최악의 시간복잡도를 생각해보니

상근이가 1을 500,000장 가지고 있고, 후보군에 있는 카드도 1이 500,000장이라면

 

바로 mid를 찾고 양 옆으로 뻗어가는 연산을 총 500,000번 그것을 후보군에 있는 카드의 수 500,000번 반복해야 하기 때문에

250,000,000,000 2500억번 연산을 해야겠다는 계산이 나왔습니다.

 

그래서 이 방법으로는 안되겠다고 생각이 들었고, 그래서 딕셔너리를 사용해서 풀이하기로 하고 5분만에 쉽게 풀 수 있었습니다.

 

상근이의 카드가 1이 몇개고 2가 몇개인지 딕셔너리로 만들어 놓고

후보군의 카드에서 상근이가 가지고 있는 카드가 있다면 찾아서 몇개인지 출력하고, 없다면 0을 출력하면 되었습니다.

소스코드

import sys
input = sys.stdin.readline

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

dic1 = {}
for x in sangen:
    if x in dic1:
        dic1[x] += 1
    else:
        dic1[x] = 1

for element in cards:
    if element in dic1:
        print(dic1[element], end=' ')
    else:
        print(0, end=' ')

느낀 점

구현을 하다가 딕셔너리를 사용하면 편하겠다고 생각하긴 했는데, 이진 탐색을 사용해서 풀고 싶어서 계속 시도했다가 엄청난 삽질을 했습니다.

여기서 미리 생각을 해두고 구현을 하는 것이 현명한 선택이라는 생각이 들었고, 앞으로는 생각을 먼저 하도록 노력하고 구현을 하다가 이 길이 아닌 것 같으면 빠르게 다시 생각하는 시간을 가져야겠다고 결심을 했습니다.