[백준] 10816번번 (python 파이썬)

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

이진탐색 풀이

 

첫 풀이 방법은

이진탐색을 한뒤 찾으려는 숫자가 있으면 count + 1을 해주고 해당 숫자를 list에서 remove한뒤 다시 그 숫자를 이진탐색하는 방식으로 하였다.

당연하게 시간초과가 나왔다.

 

두번째 풀이 방법은

찾고자 하는 숫자의 index를 이진탐색으로 찾고 그 index에서 양쪽으로 찾으려는 숫자가 있는지 반복문으로 확인하는 방식으로 하였다. 이또한 시간초과가 나왔다

list에 모든 숫자가 찾고자 하는 숫자이면 반복문이 엄청나게 돌아간다.

 

최종 풀이방법은

mid에 찾고자 하는 숫자가 나와도 이진탐색을 끝내지 않고 계속 나눠주면서 찾고자 하는 숫자의 양쪽 마지막 index를 반환한다.

2번의 이진탐색을 한다

 

n = int(input())
cards = list(map(int, input().split(' ')))
cards.sort()

m = int(input())
targets = list(map(int, input().split(' ')))

result = list()


def down_binary(target):
    left = 0
    right = len(cards) - 1

    while left <= right:
        mid = (left + right) // 2

        if cards[mid] >= target:
            right = mid - 1
        elif cards[mid] < target:
            left = mid + 1
    return left

def up_binary(target):
    left = 0
    right = len(cards) - 1

    while left <= right:
        mid = (left + right) // 2

        if cards[mid] > target:
            right = mid - 1
        elif cards[mid] <= target:
            left = mid + 1
    return left

for i in range(m):
    print(up_binary(targets[i])-down_binary(targets[i]), end=' ')

 *파이썬으로는 시간초과 -> pypy3로는 해결

 

 

다른 풀이

사전 이용 풀이

 

card의 숫자들을 dict의 key, 카드 숫자를 value로 하여 사전을 만든다.

target 숫자들을 key로하여 value를 출력한다.

n = int(input())
cards = list(map(int, input().split(' ')))
cards.sort()

m = int(input())
targets = list(map(int, input().split(' ')))

dic = dict()

for i in cards:
    if i in dic:
        dic[i] += 1
    else:
        dic[i] = 1

for i in range(m):
    if targets[i] in dic:
        print(dic[targets[i]], end=' ')
    else:
        print(0, end=' ')