[Python] 백준 풀기 10816 - 숫자 카드 2

파이썬 백준 10816번

실버4

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

10816번: 숫자 카드 2

 

 

 

 

문제 보기

분류: 자료 구조, 정렬, 이분 탐색, 해시를 사용한 집합과 맵

 

 

 

문제 풀기

이전에 풀었던 1920번 수 찾기 문제의 변형이다.

주어진 카드 범위에 대해 이분 탐색을 하여 원하는 숫자를 찾아 나가지만 답안으로 제출이 필요한 것은 그 수의 개수이다. 그 또한 중복된 숫자의 카드가 존재하기 때문에 이 부분을 해결하는데 쉽게 아이디어가 떠오르지 않았다. 찾고자 하는 숫자 카드를 발견하면 앞 뒤 index 의 값을 비교하여 지속적으로 동일한지를 검사해야 하나? 생각이 들었지만 loop가 들어가면시간 초과가 뻔할것 같아 멈추었다. 결국 검색을 통해 방법을 참고하였다.

이분 탐색을 통해 목표 숫자를 찾아 나가다가 그 숫자가 나오면 현재 탐색 구간을 count() 함수로 해당 숫자의 개수를 구하는 것이 포인트였다. 그런데 솔직히 count() 함수가 들어가면서 시간초과 걸리지 않을까 의심이 되긴했다. 문제에서 주어진 숫자 카드의 개수 범위 뿐 아니라 검색을 해야하는 숫자 M 의 범위도 적지 않기 때문이다.

이렇게 count() 함수로 구한 해당 숫자의 개수는 dictionary 로 저장하고 M 의 순서에 맞게 출력 시킨다.

 

 

 

코드 보기

import sys
inputdata = sys.stdin.readline

def fnBinaryCardSearch(n, Ncard_ls, left, right):
    if left > right:
        return 0
    
    mid = (left + right) // 2
    
    if n == Ncard_ls[mid]:
        return Ncard_ls[left:right + 1].count(n)
    elif n < Ncard_ls[mid]:
        return fnBinaryCardSearch(n, Ncard_ls, left, mid - 1)
    elif Ncard_ls[mid] < n:
        return fnBinaryCardSearch(n, Ncard_ls, mid + 1, right)
    

if __name__ == "__main__":
    N = int(inputdata().strip())
    Ncard_ls = sorted(list(map(int, inputdata().split())))
    M = int(inputdata().strip())
    M_ls = list(map(int, inputdata().split()))
    
    print(f'sorted Ncard_ls: {Ncard_ls}')         # test print
    print(f'M_ls: {M_ls}')         # test print
    
    n_dic = {}
    for n in Ncard_ls:
        left = 0
        right = len(Ncard_ls) - 1
        if n not in n_dic:
            n_dic[n] = fnBinaryCardSearch(n, Ncard_ls, left, right)
            
    print(f'n_dict: {n_dic}')           # test print
    print(' '.join(str(n_dic[x]) if x in n_dic else '0' for x in M_ls ))



# 10
# 6 3 2 10 10 10 -10 -10 7 3
# 8
# 10 9 -5 2 3 4 5 -10

# sorted Ncard_ls: [-10, -10, 2, 3, 3, 6, 7, 10, 10, 10]
# M_ls: [10, 9, -5, 2, 3, 4, 5, -10]
# n_dict: {-10: 2, 2: 1, 3: 2, 6: 1, 7: 1, 10: 3}
# 3 0 0 1 2 0 0 2