[파이썬] 백준 10816 : 숫자 카드2

[파이썬] 백준 10816 : 숫자 카드2

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

10816번: 숫자 카드 2

실버 4

자료구조, 정렬, 이분 탐색

 

1 : 해시 자료구조를 이용한 코드(1184ms)

import sys
input = sys.stdin.readline

N = int(input())
cards = sorted(list(map(int, input().split())))
M = int(input())
candidate = list(map(int, input().split()))

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

for i in range(M):
    a = candidate[i]
    if a in count.keys():
        print(count[a], end=' ')
    else:
        print(0, end=' ')

해시 자료구조는 해시맵에서 해당 주소에 값이 없으면 값을 새로 추가하고

있으면 그 값에 더해주는 방법이다. 파이썬에서는 딕셔너리를 사용해 만들 수 있다.

 

N은 숫자 카드의 개수.

두번째 줄은 N개의 카드에 어떤 수가 적혀있는지 리스트로 입력을 받는다.(cards)

M은 후보카드들의 개수,

네번째줄에는 후보카드들에 어떤 수가 적혀있는지 리스트로 입력 받는다.(candidate)

 

각각의 후보카드가 cards에 몇개가 존재하는지를 하나씩 하나씩 출력해야 한다.

 

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

count라는 이름의 딕셔너리를 선언한다.

cards에 입력받은 상근이의 카드의 번호를 key값으로, 각각의 개수를 value값으로 뽑아낼 수 있다.

예제 입력 1의 경우

6 3 2 10 10 10 -10 -10 7 3가 입력되었고 입력받음과 동시에 리스트로 형변환 후 sorted로 정렬시켰으므로

cards = [-10 -10 2 3 3 6 7 10 10 10] 가 된다.

반복문을 통해 이를 딕셔너리로 뽑아내면

count = {-10 : 2, 2 : 1, 3: 2, 6 : 1, ....} 와 같은 형태가 만들어진다.

key값은 카드의 번호, value값은 해당 카드의 개수이다.

 

 

for i in range(M):
    a = candidate[i]
    if a in count.keys():
        print(count[a], end=' ')
    else:
        print(0, end=' ')

딕셔너리.keys()는 해당 딕셔너리의 key값만을 반환하는 함수이다.

네번째 줄에 입력한 후보카드(candidate) 중에 10이 있다면 cards안에 10번 카드가 몇 개가 있는지를 반환하도록 한다.

후보카드에 있는 카드가 cards에 없는 경우에는 0을 출력하도록 만들어야 에러가 나지 않는다.

 

https://afterdawncoding.tistory.com/93

[파이썬] 딕셔너리(Dictionary) 자료형 정리

 

위의 for문을 다음과 같이 바꾸면 시간이 조금 빨라진다. (944ms)

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

딕셔너리.get(key값) 함수는 딕셔너리[key값]과 동일하게 해당 딕셔너리의 key값에 대한 value값을 반환한다.

그러나 주어진 문제에서는 후보 카드의 숫자가 상근이의 카드들의 숫자와 항상 일치하지는 않는다.

따라서 result = count[target]으로 하면 keyerror가 나타날 수 있다.

 

get함수의 경우 딕셔너리에서 찾고자 하는 key값이 존재하지 않으면 None이 반환된다.

따라서 값이 None이 나올경우 0이 출력되도록 하면 에러없이 실행이 된다.

 

 

아니면 for문 대신 그냥 이렇게 해도 된다.

 

print(' '.join(str(count[m]) if m in count else '0' for m in candidate))

join은 문자열을 구분자로 구분해주므로 count[m]을 str으로 형변환 해주어야 한다.

 

 

 

 

2 : 이진 탐색 함수 bisect를 이용한 풀이

import sys
from bisect import bisect_left, bisect_right

input = sys.stdin.readline

def bisearch(x, left, right):
    l = bisect_left(x, left)
    r = bisect_right(x, right)
    return r - l

N = int(input())
cards = sorted(list(map(int, input().split())))
M = int(input())
candidate = list(map(int, input().split()))

for i in range(M):
    print(bisearch(cards, candidate[i], candidate[i]), end = ' ')

파이썬에는 이진 탐색을 간편하게 만들 수 있는 bisect 라이브러리를 지원한다.

자세한 설명은 이곳을 참조.

 

https://afterdawncoding.tistory.com/97

[파이썬] 이진 탐색 라이브러리 bisect