[백준] 10816번 : 숫자 카드 2 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

10816번: 숫자 카드 2

 

1. 문제 설명

2. 풀이과정

해당 문제는 이진 탐색을 활용하여 오름차순으로 정렬된 숫자의 리스트에서 구하고자 하는 숫자의 위치를 빠르게 찾아내고, 찾아낸 범위에서 해당 숫자의 개수를 세어 딕셔너리로 저장하며 해결할 수 있다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. 숫자 카드의 개수를 입력받는다. N = int(sys.stdin.readline())
3. 숫자 카드에 적혀있는 수를 리스트로 입력받는다. card = list(map(int, sys.stdin.readline().split()))
4. 개수를 구할 숫자 카드를 입력받는다. M = int(sys.stdin.readline())
5. 개수를 구할 숫자 카드를 리스트로 입력받는다. num = list(map(int, sys.stdin.readline().split()))
6. 개수를 빠르게 계산하기 위해 카드 위치를 이진 탐색으로 찾는다. 하여 이진 탐색을 수행할 함수를 생성한다. def binary_search(target, data, start, end)
7. 이진 탐색 함수에서 만약 시작 위치가 끝 위치를 넘어갔다면 0을 반환한다. if (start > end): return 0
8. 그게 아니라면 중간 위치를 구한다. center = (start + end) // 2
9. 만약 중간에 위치한 값이 찾고자 하는 숫자이면 if (data[center] == target)
10. 시작과 끝 범위 안에서 찾는 숫자의 개수를 반환한다. return data[start : end + 1].count(target)
11. 만약 중간에 위치한 값이 찾고자 하는 숫자보다 작으면 elif (data[center] < target)
12. 중간 위치의 다음 위치를 시작으로 하여 범위를 새로 조정하고 이진 탐색을 다시 수행한 결과를 반환한다. return binary_search(target, data, center + 1, end)
13. 그것도 아니라면 (중간에 위치한 값이 찾고자 하는 숫자보다 크면) else
14. 중간 위치의 이전 위치를 끝으로 하여 범위를 새로 조정하고 이진 탐색을 다시 수행한 결과를 반환한다. return binary_search(target, data, start, center - 1)
15. 숫자 카드에 적혀있는 수를 이진 탐색하기 위해 오름차순으로 정렬한다. card.sort()
16. 숫자 카드 개수를 저장할 딕셔너리를 생성한다. d = {}
17. 숫자 카드를 세트 자료구조로 바꾸어 중복 없이 하나씩 추출한다. for i in set(card)
18. 이진 탐색 함수를 활용하여 해당 카드의 개수를 구한 뒤, 카드의 숫자를 key로 하고 카드의 개수를 value로 저장한다. d[i] = binary_search(i, card, 0, len(card) - 1)
19. 개수를 구할 숫자 카드를 하나씩 추출하여 만약 카드 개수를 저장한 딕셔너리에 값이 있으면 카드 개수를 문자열로 연결하고 없다면 0을 연결하여 출력한다. print(' '.join(str(d[i]) if i in d else '0' for i in num))
20. 각 문자열은 공백으로 연결하여 출력한다.

반응형

3. 소스코드

import sys

N = int(sys.stdin.readline())
card = list(map(int, sys.stdin.readline().split()))
M = int(sys.stdin.readline())
num = list(map(int, sys.stdin.readline().split()))

def binary_search(target, data, start, end):
    if (start > end):
        return 0
    
    center = (start + end) // 2
    if (data[center] == target):
        return data[start : end + 1].count(target)
    elif (data[center] < target):
        return binary_search(target, data, center + 1, end)
    else:
        return binary_search(target, data, start, center - 1)

card.sort()
d = {}
for i in set(card):
    d[i] = binary_search(i, card, 0, len(card) - 1)

print(' '.join(str(d[i]) if i in d else '0' for i in num))