[백준] 10816번 숫자 카드2, 시간 초과 - 이진탐색 + 알파

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

10816번: 숫자 카드 2

 

처음엔 count()를 이용하여 몇 개가 들어갔는지 구하였다.

그렇게 하니 시간복잡도가 O(n^2)으로 2% 대에서 시간 초과가 나왔다.

 

그래서 이진탐색 사용

# BOJ_10816
import sys

# 입력
n = int(input())
cards = list(map(int, sys.stdin.readline().split()))
m = int(input())
numbers = list(map(int, sys.stdin.readline().split()))

cards.sort()

def binary_search(target, data):
    start = 0
    end = len(data) - 1
    while start <= end:
        mid = (start + end) // 2
        if data[mid] == target:
            return mid
        elif data[mid] < target:
            start = mid + 1
        else:
            end = mid - 1
    return None


# 각 numbers 리스트에 있는 숫자 몇 개인지 출력하기
for number in numbers:
    num_count = 0
    start_index = binary_search(number, cards)
    if start_index == None:
        print(num_count, end=" ")
        start_index = 0
    else:
        num_count = 1
        idx = start_index
        while idx <= len(cards) - 2:
            idx += 1
            if cards[idx] == number:
                num_count += 1
            else:
                break
        idx = start_index
        while idx >= 1:
            idx -= 1
            if cards[idx] == number:
                num_count += 1
            else:
                break
        print(num_count, end=" ")

 

 

65%에서 시간초과가 나왔다.

결국엔 nlogn이 가장 최대로 줄인 것 같은데..

 

질문게시판을 찾아보니

target이 처음 나타나는 인덱스를 target_start

target가 마지막으로 나타나는 인덱스를 target_end

라고 하면

타겟의 갯수는 target _end - target_start + 1로 출력하면 된다.

 

# BOJ_10816
import sys

# 입력
n = int(input())
cards = list(map(int, sys.stdin.readline().split()))
m = int(input())
numbers = list(map(int, sys.stdin.readline().split()))

cards.sort()
# print(cards)

def binary_search(target, data):
    start = 0
    end = len(data) - 1
    while start <= end:
        mid = (start + end) // 2
        if data[mid] == target:
            target_start = mid
            target_end = mid
            while target_start >= 1:
                if data[target_start - 1] == target:
                    target_start -= 1
                else:
                    break
            while target_end <= len(data) - 2:
                if data[target_end + 1] == target:
                    target_end += 1
                else: # target과 다름
                    break
            # print(target, target_end, target_start)
            return target_end - target_start + 1
        elif data[mid] < target:
            start = mid + 1
        else:
            end = mid - 1
    return 0


# 각 numbers 리스트에 있는 숫자 몇 개인지 출력하기
for number in numbers:
    print(binary_search(number, cards), end=" ")

 

아.. 또 65%에서 시간초과..

if data[mid] == target:
    target_start = mid
    target_end = mid
    while target_start >= 1:
        if data[target_start - 1] == target:
            target_start -= 1
        else:
            break
    while target_end <= len(data) - 2:
        if data[target_end + 1] == target:
            target_end += 1
        else: # target과 다름
            break
    # print(target, target_end, target_start)
    return target_end - target_start + 1

이부분을 또 이진탐색으로 만들어야 해서 그런가..

 

https://aigong.tistory.com/396

[Baekjoon] 10816번 : 숫자 카드 2 (Python, 이분 탐색)

 

정답을 보니 딕셔너리로 구현하였다.

지금 이해하기엔 어려워서 보류... 
ㅠㅜㅠ