글 읽기 - 시간초과.. 더 나은 알고리즘이 있나요?

minqw5 7년 전 0

-999 -500 -200 7 33 76 455 500 800

테스트 케이스가 이럴 경우 이진탐색 & 절대값 이용해서 -500, 500을 찾아 낼 수 있습니다.

하지만 만약

-999 -500 -200 7 33 76 455 510 800

이렇게 될 경우 어떻게 -500과 510을 찾아내야 하나요? 이부분에서 for 문을 두 개 돌리는데 시간초과가 나는것 같습니다.

(51줄 ~ 59줄) Python3 코드.

이 경우도 이진탐색을 적용할 수 있나요?

이런 예외를 어떻게 처리해야 할지 궁금합니다

def binarySearch(alist, item):
    first =  0
    last = len(alist) -1
    found = False 
  
    while first<=last and not found: 
        midpoint = (first + last)// 2
        if alist[midpoint] == item: 
            found = True 
        else: 
            if item < alist[midpoint]: 
                last = midpoint - 1
            else: 
                first = midpoint + 1
    return found
i = 0
t = 0
min_value = 1000000001
a = int(input())
s = [int(x) for x in input().split()]

s.sort()

ma = (n for n in s if n < 0)
plus = (n for n in s if n > 0)

ma = list(ma)
plus = list(plus)

if not list(plus):
    ma = list(reversed(list(ma)))
    i = 0
    for x in ma:
        if i == 2:
            break
        print (x,end=" ")
        i+=1
elif not list(ma):
    i = 0
    for x in plus:
        if i == 2:
            break
        print (x,end=" ")
        i+=1
else:
    for x in ma:
        if binarySearch(plus,abs(x)):
            print (x,abs(x))
            i = 1
            break
if not i:
    for x in ma:
        for y in plus:
            t = abs(x + y)
            if min_value > t:
                min_value = t
                idx_plus = plus.index(y)
                idx_ma = ma.index(x)
    print (ma[idx_ma],plus[idx_plus])

yukariko 7년 전 1

이진 탐색의 원리를 이용하시면 됩니다.

이진탐색은 정렬된 배열에서 범위를 반으로 좁혀가며 원하는 숫자를 찾는 알고리즘입니다.

그러면 탐색과정에서 최종적으로 숫자를 찾지 못하더라도, 끝나기 직전의 범위는 우리가 원하는 숫자가 있을 수 있는 가장 유력한 범위일 것입니다.

그러면 그 범위안에 있는 숫자가 찾는 숫자와 가장 비슷한 숫자라고 할 수 있겠죠.

그걸 이용하면 합이 0인 숫자 뿐만아니라 합이 0과 가장 가까운 숫자를 찾을 수 있습니다.

minqw5 7년 전 0

답변 잘 들었습니다.

다만 처음에 어떤것을 기준으로 찾아가야 하는건가요? 제 질문 2번째 케이스 예를 들어 주실 수 있으신가요?

yukariko 7년 전 0

배열의 각 숫자에 대해 반복하면서 그 반대가 되는 (합이 0이 되는) 숫자를 찾으면 될 것입니다.

예를들어 -999에 대해서 999를 찾으면 되고

-500이라면 500을 찾으면 되겠죠.

하지만 999도 500도 존재하지 않습니다. 따라서 앞서말한 가까운 숫자를 찾는 과정을 통해 이를 해결하실 수 있습니다.

minqw5 7년 전 0

-999 -500 -200 7 33 76 455 507 800

이럴 경우 대략 순서가 -999에 대해 999찾아보고 -500에 대해 500 찾아보고 -200에 대해서 200 찾아보고

이런식으로 가다가 양수에서는 어떻게 판단해야하나요? 설명해주신 부분 "끝나기 직전의 범위"는 위에 있는 테스트케이스에서

어디쯤 해당하는건지 알려주시면 안될까요?

naong606 7년 전 0

-500에 대해 500을 이진검색으로 찾을 때 범위를 좁혀나가다 보면

아마 [455, 507] 범위에서 500을 찾지 못하고 종료할텐데,

이 때 455랑 507이 입력된 값들 중에 500과 제일 가까운 값들이기 때문에

-500과 더했을 때 0과 가장 가깝게 되는 두 후보가 될 것입니다.

아마 yukariko님이 말씀하신 "끝나기 직전의 범위"는 위의 [455, 507]과 같은 범위를 말하신 게 아닌가 싶네용

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

문제

문제

출처

ICPC

시간초과.. 더 나은 알고리즘이 있나요?

minqw5 7년 전 0

yukariko 7년 전 1

minqw5 7년 전 0

yukariko 7년 전 0

minqw5 7년 전 0

naong606 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말