백준 2473번 파이썬 문제풀이(세 용액)

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

2473번: 세 용액

---

 

O(n^2) 에 해결할 수 있기 때문에 잘생각해보면 리스트 전체의 각 지점을 반복문을 돌면서 한점을 기준으로 잡고 바로 오른쪽을 시작점 마지막 인덱스를 끝지점으로 투포인터를 돌리면 되는 간단한 문제이다. 세개의 점을 찾아야하기 때문에 투포인터의 응용버전이라 조금 생소할 수도 있지만 이기회에 잘 익히자. 

(참고로 N^2 임에도 불구하고 아주큰수의 + 연산때문에 파이썬3에서는 시간초과가 발생한다. pypy3로 제출하자)

 

N = int(input())
arr = list(map(int, input().split()))
arr.sort()

ans = []  # i,s,e 순서
min_ = 1 << 40
for i in range(N - 2):
    # 출발점을 i + 1, 끝점을 N - 1로 잡는다.
    s, e = i + 1, N - 1

    while s < e:
        sum_ = arr[i] + arr[s] + arr[e]

        if abs(sum_) < abs(min_):
            min_ = sum_
            ans = [arr[i], arr[s], arr[e]]

        if sum_ < 0:
            s += 1
        elif sum_ > 0:
            e -= 1
        else:
            print(*sorted(ans))
            exit()

print(*sorted(ans))