study/알고리즘 문제 풀이

[python] 10816 숫자 카드 2 (Hash)

dddzr 2023. 6. 4. 20:44

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 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개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

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

 

10816번: 숫자 카드 2

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

www.acmicpc.net

 

- 풀이

hash를 이용하여 푸는 문제입니다.

key: 숫자, vaule:카드 수

hash

  • key, value로 이루어진 자료구조
  • 모든 자료형으로 접근이 가능하다

파이썬에서 hash는 딕셔너리로 구현합니다.

 

n = input()
cardList = {}
a = list(map(int, input().split()))
for i in range(0, len(a)):
  num = a[i]
  if num in cardList:
    cardList[num] += 1
  else:
    cardList[num] = 1

m = input()
b = list(map(int, input().split()))
for i in range(0, len(b)):
  num = b[i]
  if num in cardList:
    print(cardList[num], end=" ")
  else:
    print(0, end=" ")

파이썬 문법

1. 딕셔너리 초기화

dictionary = {}

2. key 포함여부

key in dictionary

처음에 dictionary[num] is None, dictionary[num] == Null을 사용하려고 했는데

파이썬에서 Null은 is None으로 표현하고 딕셔너리[key]는 해당키가 존재하지 않으면 에러가 나서 in키워드로 포함여부를 확인해야 했습니다.

 

3. print 한줄에 하기

print("string", end=" ")

문자열 끝에는 기본적으로 개행문자인 \n이 들어가기 때문에 print를 반복적으로 할 경우 줄바꿈이 됩니다.

print함수의 end파라미터 값을 바꾸어 한 줄에 출력할 수 있습니다.

 

- 코드 개선

1. 딕셔너리의 get() 메서드를 사용

cardList.get(num, 0)

2 .Counter 사용

collections 모듈의 Counter 클래스를 사용하면 간단하게 카드 카운트를 수행할 수 있습니다. Counter는 각 요소의 개수를 딕셔너리로 저장합니다. 

cardList = Counter(a)

 

수정한 코드

from collections import Counter
n = input()
a = list(map(int, input().split()))

# 카드 카운트
cardList = Counter(a)

m = input()
b = list(map(int, input().split()))

# 검색 및 출력
for num in b:
    print(cardList.get(num, 0), end=" ")

 

- 결과

에러난거 빼고 밑에서 부터 기존코드에 1. get메서드 2.counter 를 적용시킨 결과입니다.