[BOJ] 10816 / 숫자 카드 2 / Python 파이썬

[BOJ] 10816 / 숫자 카드 2 / Python 파이썬

[BOJ] 10816 / 숫자 카드 2 / Python 파이썬

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

10816번: 숫자 카드 2

 

풀이

[BOJ] 10815 / 숫자 카드 문제의 응용 문제이다.

 

처음 시도로는 해당하는 카드의 index 를 이분탐색을 진행하여 찾고, 그 index 를 기준으로 앞뒤를 탐색하는 방법을 구상하였지만 시간초과가 되어버렸다.

 

그 다음으로는 index 를 시작 숫자로 하여 다시 이분탐색을 하는 방법을 사용 하였지만, 이분탐색은 mid 값을 찾는 방법이기때문에 해당하는 숫자의 범위의 양 끝을 찾을 수 없었다.

 

주어진 여러개의 숫자의 개수를 세어주는 방법이 필요한 상황 이었는데, 참고 블로그를 통해 너무나 간단히 해결 할 수 있었다.

그 방법은 주어진 card 의 중복을 미리 count 해두고 해당하는 card 를 이분탐색으로 찾을때 불러오는 방법이었다.

 

N = int(input())
cards = list(map(int, input().split()))
cards.sort()
cardsDic = {}

for c in cards:
    if c not in cardsDic:
        cardsDic[c] = 1
    else:
        cardsDic[c] += 1

M = int(input())
nums = list(map(int, input().split()))


for n in nums:
    start = 0
    end = N-1

    while start <= end:
        mid = (start+end)//2

        if cards[mid] == n:
            break

        if cards[mid] > n:
            end = mid - 1
        else:
            start = mid+1
    if cards[mid] == n:
        print(cardsDic[n], end=" ")
    else:
        print(0, end=" ")

※ 이분 탐색 문제라는 주제에 매몰되어 다양한 해결을 생각하지 못하였다.

 

 

---

참고 블로그

https://infinitt.tistory.com/288

백준 (boj) 파이썬 - 10816 번 : 숫자 카드2