글 읽기 - 해당 소스가 왜 시간초과가 나는지 설명부탁드립니다

snu_steven 3년 전 0

binary search 로 count 범위를 줄이면서 풀이했는데 어느 부분에서 시간을 많이 잡아먹어서 시간초과가 나는지 잘 모르겠습니다. 고수님들 설명 부탁드립니다!

import sys
input = sys.stdin.readline

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

n = input()
N = sorted(map(int, input().split()))
m = input()
M = map(int, input().split())

for i in M:
    print(binary_search(i, 0, len(N)-1, N), end=' ')

nahwasa 3년 전 0

binary_search 시 13line 부분이 O(N) 만큼 걸릴걸로 예상됩니다.

따라서 21,22 line에서 O(MNlogN) 으로 시간초과가 나게 됩니다.

이 문제의 경우 사실 O(1)로 바로 찾을 수 있는 방법이 있긴하니 효율적으로 가시려면 로직 자체를 변경해보시면 좋을듯합니다.

다만 이 코드 로직으로도 좀 변경하면 통과 가능할것같긴합니다.

M이 50만개에 1초제한이므로 (파이썬은 가중치 있음)

현재 로직을 좀 변경해서 흔히 c++에서 사용하는 lower_bound, upper_bound를 구현하셔서(파이썬에서 이미 제공되는진 모르겠음)

해당 값의 갯수를 세셔도 시간내에 아슬아슬하게 될것같긴합니다.

[-1, 0, 1, 1, 1, 3, 4] 이런식으로 정렬된 배열이 있을 경우 0에 대한 lower_bound는 idx 2의 위치를 가르키고, upper_bound는 idx 4에 해당하는 위치를 가르키는 함수입니다.

binary_search를 좀만 변경하면 됩니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

해당 소스가 왜 시간초과가 나는지 설명부탁드립니다

snu_steven 3년 전 0

nahwasa 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말