글 읽기 - 시간초과가 뜹니다ㅠㅠ

hssk1528 6년 전 0

이분탐색으로 석순과 종유석의 길이가 해당 길이보다 길거나 같은 경우를 찾아서 계산했는데

어디서 시간초과가 나는지 모르겠습니다ㅠㅠ

이분탐색의 알고리즘이 잘못된건가요??

length = input().split()
n = int(length[0])
h = int(length[1])
mite = [0]*(int(n/2))
cite = [0]*(int(n/2))

def binarySearch(length,lst):
    left = 0
    right = int((n/2))
    res = 0
    
    while left < right:
        mid = int((left+right)/2)
        if lst[mid] < length:
            left = mid+1
        else:
            right = mid
    return right

for i in range(int(n/2)):
    mite[i] = int(input())
    cite[i] = int(input())

mite.sort()
cite.sort()
obsNum = [0]*(h+1)

for i in range(1,(h+1)):
    obsNum[i] = ((int(n/2))-binarySearch(i,mite))+((int(n/2))-binarySearch(h-i+1,cite))

obsNum[1] = int(n/2)
obsNum[h] = int(n/2)

result = min(obsNum[1:])
cnt = obsNum.count(result)

print(result,cnt)

jh05013 6년 전 0

acmicpc.net/problem/15552

hssk1528 6년 전 0

조언 감사합니다!

그런데 입력 방식을 바꾸어도 똑같이 시간초과가 뜨네요ㅠㅠ

그게 문제가 아닌가봅니다ㅠㅠ다른 내장 함수들을 쓰는게 문젠지..뭔지 모르겠네요...ㅠㅠ

jh05013 6년 전 0

오름차순 정렬된 리스트에서 이분탐색을 하는 모듈이 있습니다. bisect 모듈을 찾아 보세요.

이것을 사용해도 시간초과가 나온다면 Pypy 3로 제출해 보세요. 같은 파이썬3 문법인데 훨씬 빠릅니다.

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

문제

문제

출처

ICPC

시간초과가 뜹니다ㅠㅠ

hssk1528 6년 전 0

jh05013 6년 전 0

hssk1528 6년 전 0

jh05013 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말