백준 알고리즘: 10816번 숫자 카드 2 (Python)

문제 정보

---

10816번: 숫자 카드 2

 

 

핵심

---

주어지는 숫자의 개수는 1 <= N <= 500,000 이고, 숫자는 -10,000,000 <= n <= 10,000,000 이다

숫자의 범위가 너무 크기 때문에, 배열을 활용한 풀이는 불가능할 것이라 판단하였고 또한 이분탐색같은 알고리즘을 사용하기에도 살짝 무리가 있어보였다

따라서 해시-딕셔너리를 이용하여 문제를 풀이하였고, 상근이가 가지고 있는 숫자 카드를 key로 하여 해시에 넣고 value는 해당 숫자카드의 개수를 입력해준다

중복을 허용하기 때문에 해당 key가 존재한다면 value는 1씩 늘려주어서 가지고있는 숫자 카드의 개수를 표현해 줄 수 있다

마지막으로, 몇개 가지고 있는 숫자카드인지 구해야할 카드들을 해시의 get 함수를 활용하여 있는지 판단하고(O(1)) 있다면 value(가진 숫자카드의 개수)를 출력해주는 방식으로 풀이하였다

 

풀이

---

import sys

com = sys.stdin.readlines()[1:]
sg = dict()
for c in com[0].strip().split():
    if c not in sg:
        sg[c] = 1
    else:
        sg[c] += 1

print(' '.join(str(sg.get(n, 0)) for n in com[2].strip().split()))

 

sg 는 딕셔너리로 해시의 성질을 가지고 있다

상근이가 가지고있는 카드를 딕셔너리에 추가하고, 이미 추가했었다면 1씩 더해주는 방식으로 카운팅한다

마지막으로, 몇개 가지고있는지 판단할 카드의 숫자들을 dict.get() 함수를 통하여 value를 얻어올 수 있으며 두번째 인자로 해당 key가 존재하지 않다면 리턴할 값으로 0을 설정해 주었다

 

고찰

---

다른분의 풀이를 봤는데, Counter 를 사용하는 분들이 많았던것 같다

counter도 마찬가지로 해시를 기반으로 한 라이브러리로 해당 배열의 요소들을 카운팅 해주는 유용한 라이브러리인것 같다

from collections import Counter

C = Counter(N)
print(' '.join(f'{C[m]}' if m in C else '0' for m in M))

Counter() 의 인자로 배열을 주면, 해당 배열에 있는 요소들을 카운팅해서 해시 테이블로 반환해준다

in 키워드를 사용하여 몇개인지 판단할 요소들이 카운터에 존재하는지 판단하고,

파이썬의 f-string 기능을 활용하여 문자열 내에서 변수의 값을 출력해줄 수 있다

f-string에 대한 내용은 구글링하다 찾은 한 블로그를 참고해보면 좋을것 같아 첨부한다!

 

 

참조

---

파이썬의 f-string으로 문자열 포멧팅하기

GitHub - dduneon/CodingTestPy