bj2473 세 용액

문제

• 백준 URL: 세 용액
• 난이도 골드 3

풀이

import sys

input = sys.stdin.readline
n = int(input())
solutions = sorted(list(map(int,input().split())))
min_sum = float('inf')
final_answer = []

for i in range(n-2):
    solution = solutions[i]
    l = i+1
    r = n-1
    
    while l < r:
        current_sum = solution + solutions[l] + solutions[r]
        
        if abs(current_sum) < min_sum:
            min_sum = abs(current_sum)
            ans = [solution, solutions[l], solutions[r]]
        
        if current_sum < 0: l += 1
        elif current_sum > 0: r -= 1
        else: exit(print(*ans))
        
print(*ans)

가장 간단한 방법은 세 개의 용액을 선택하는 모든 경우의 수를 탐색하는 것이다. 하지만 이 방법은 시간 복잡도가 O(N³)이 되어 N이 5,000일 경우 시간 초과가 발생한다.

따라서 더 효율적인 접근 방식이 필요하다. 이 문제는 정렬과 투 포인터 알고리즘을 결합하여 O(N²) 시간 복잡도로 해결할 수 있다.

1. 먼저 주어진 용액의 특성값 리스트를 오름차순으로 정렬한다. 정렬을 통해 투 포인터 기법을 효과적으로 사용할 수 있다.
2. 첫 번째 용액부터 순서대로 하나를 고정한다. 이 고정된 용액을 기준으로 나머지 두 용액을 찾는다.
3. 고정된 용액을 제외한 나머지 용액들 중에서 두 개의 용액을 선택한다. 이때, 탐색 범위를 좁히기 위해 투 포인터 기법을 사용한다.
   • left 포인터는 고정된 용액 바로 다음에서 시작한다.
   • right 포인터는 리스트의 가장 끝에서 시작한다.
   • 세 용액(고정된 용액, left 포인터 용액, right 포인터 용액)의 특성값 합을 계산한다.
4. 포인터 이동 및 정답 갱신:
   • 계산된 합이 0보다 작으면, 합을 더 크게 만들기 위해 left 포인터를 오른쪽으로 한 칸 이동시킨다.
   • 합이 0보다 크면, 합을 더 작게 만들기 위해 right 포인터를 왼쪽으로 한 칸 이동시킨다.
   • 만약 합이 0이면, 완벽한 답을 찾았으므로 탐색을 종료한다.
   • 매 단계에서 계산된 합의 절댓값이 이전에 찾았던 최솟값보다 작으면, 현재 세 용액을 정답으로 갱신한다.

이 과정을 모든 용액에 대해 반복하여 0에 가장 가까운 합을 만드는 세 용액을 찾는다.