글 읽기 - python 시간초과

dhyang24 3년 전 0

이분탐색을 이용하여 각 수에 대한 가장 가까운 합을 구한 다음, 그 합들의 최소값의 개수를 구하는 방식으로 알고리즘을 짰습니다.

제가 계산하기로는 O(nlogn+α) 가 나오는데(잘못 계산했을수도 있습니다) 시간초과가 나옵니다.

방식 자체가 잘못된건가요, 아니면 방식을 구현하는데 최적화를 잘못한건가요?

import sys
import os
for i in range(int(sys.stdin.readline())):
    #입력
    a,b = map(int,sys.stdin.readline().split())
    c = sorted(map(int,sys.stdin.readline().split()))
    #d: 정답 저장 리스트
    d = []
    gz = min(c)
    pz = max(c)
    for l in range(len(c)):
        #만약 l과 가장 작은 수를 더해도 b에 가장 작은 d를 더한경우보다 크거나, l과 가장 큰 수를 더해도 b에 가장 작은 d를 뺀 경우와 같을 경우 탐색 건너뜀.
        if len(d) != 0:
            if l + gz < b + d[0] or l + pz + d[0] > b:
                pass
            else:
                continue
        #같은 수끼리 더하지 않게 함
        e = c.copy()
        e.remove(c[l])
        #이분탐색, 각 수에 대해 합이 가장 가까운 두 수를 찾음
        mn = 0
        mx = len(e)-1
        while mn+1 != mx:
            mid = (mn+mx)//2
            if c[l]+e[mid] == b:
               mx = mid
               mn = mid
               break
            elif c[l] +e[mid] > b:
               mx = mid
            elif c[l] + e[mid] < b:
                mn = mid
        #이분탐색으로 나온 가장 가까운 두 수에 대해 계산       
        dea = abs(c[l]+e[mn]-b)
        deb = abs(c[l]+e[mx]-b)
        de = min(dea,deb)
        #정답 저장하는 수열의 첫번째 값과 과 비교
        if len(d) == 0 or d[0] > de:
            #정답 수열의 첫번째 값보다 작다면 정답 수열을 초기화하고 값을 추가.
            d = [de]
            if dea == deb:
                if mn != mx:
                    #만약 이분탐색으로 나온 두 수가 같다면 두번 추가
                    d.append(de)
            #만약 정답수열의 첫번째 값과 같다면 정답 수열에 추가.
        elif d[0] == de:
            if dea == deb:
                if mn != mx:
                    #만약 이분탐색으로 나온 두 수가 같다면 두번 추가
                    d.append(de)
            d.append(de)
    #d의 길이 //2 를 출력.
    sys.stdout.write(str(len(d)//2)+'\n')

dhyang24 3년 전 0

copy랑 remove때문에

nlogn이 아닌 n^2가 나오는군요...

시간복잡도 문제는 해결했습니다.

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

문제

문제

출처

ICPC

python 시간초과

dhyang24 3년 전 0

dhyang24 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말