[백준 2473] 세 용액 - 파이썬(Python)

 

 

문제

---

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

2473번: 세 용액

 

나의 풀이

---

그냥 n개의 원소 중 임의의 3개를 뽑아서 합을 구하는 방식으로 하게 되면 시간복잡도가 O(n^3)까지 올라가게 된다. 따라서 투 포인터를 사용해서 O(n^2)으로 풀어야 통과할 수 있다. i를 0~n-2까지 순회하면서 left와 right를 바꿔주어야 한다. 아래 코드는 python으로는 시간초과가 나왔고 pypy로 통과하였다. 서치를 해보니 대부분의 해답들이 pypy로 제출해 통과하였고, python으로 제출해 통과하려는 경우엔 iter를 사용해 좀 더 python스럽게 코드를 작성해야 한다.(하지만 이게 본 문제 알고리즘 풀이의 핵심이 아니므로 넘어가도록 한다.)

투 포인터(그림 출처 : cieske tistory)

 

코드

---

# https://www.acmicpc.net/problem/2473
import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().strip().split()))
arr.sort()
ans = [0, 0, 0]
res = float('inf')

for i in range(N-2):
    l, r = i+1, N-1
    while l < r:
        curr = arr[i] + arr[l] + arr[r]
        if abs(curr) < abs(res):
            ans = [arr[i], arr[l], arr[r]]
            res = curr
        if curr > 0:
            r -= 1
        elif curr < 0:
            l += 1
        else:   # curr == 0
            print(arr[i], arr[l], arr[r])
            sys.exit()
for num in ans:
    print(num, end=' ')