[Python] BOJ 2473 - 세 용액

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

2473번: 세 용액

# 저번주에 풀었던 '두 용액'에서 한번 더 응용한 문제이다.

 

# 당연히 전체 용액 중 3개를 뽑아 다 구하는 NC3풀이는 안되고

   '두 용액' 풀이처럼 투 포인터를 사용하였다.

 

# N이 5000이하여서 반복문을 돌며 용액을 하나 고르고 나머지 N-1개의 용액에서

   투 포인터를 사용하여 답을 구했다.

   이러면 처음에 용액을 고르는데 O(N), 투 포인터를 사용하면 O(N)이어서 O(N^2)이 된다.

 

1. 우선 1번째 용액부터 N-2번째 용액까지 i가 돌며 용액을 하나 고른다.

     그리고 j에 i+1, k에 마지막인덱스인 N-1을 넣어주고 투 포인터를 사용한다.

 

2. '두 용액'과 마찬가지로 i, j, k 포인터가 가리키는 값의 합이 0이면 바로 세 수를 출력하고 종료한다.

 

   2-1. 세 용액의 합이 현재 최소 합인 diff보다 작으면 diff값을 갱신해주고

                 ans에 세 용액을 저장한다.

 

   2-2. 세 용액의 합이 0보다 크면 k를 1 감소시키고, 0보다 작으면 j를 1 증가시킨다.

                 j가 k보다 같거나 커지면 while문을 종료하고 i를 다음 용액으로 바꿔준다.

 

3. 마지막에 ans를 출력해준다.

 

import sys
input = sys.stdin.readline
N = int(input())
nums = list(map(int,input().split()))
diff = 3000000001
nums.sort()

for i in range(N-2):
    j, k = i+1, N-1
    while j < k:
        if nums[i] + nums[j] + nums[k] == 0:
            ans = [nums[i], nums[j], nums[k]]
            ans.sort()
            print(*ans)
            sys.exit(0)

        if abs(nums[i]+ nums[j] + nums[k]) < diff:
            diff = abs(nums[i]+ nums[j] + nums[k])
            ans = [nums[i], nums[j], nums[k]]

        if nums[i] + nums[j] + nums[k] > 0:
            k -= 1
        elif nums[i] + nums[j] + nums[k] < 0:
            j += 1

print(*ans)

(solved.ac 티어: 골드 4)