Baekjoon 2473. 세 용액 / Python

알고리즘 설명

문제 설명

서로 다른 세 개의 용액의 값의 합이 0에 가장 가까운 경우를 찾는다.

코드 설명

용액들을 정렬한다.
중간 포인터를 모든 인덱스를 순회하면서, 첫 번째 인덱스와 마지막 인덱스를 이동시키면서 투 포인터 방식으로 값을 찾는다.

시간복잡도 : 정렬 O(n log n) + 투포인터 O(n ^ 2)

import sys
input = sys.stdin.readline

n = int(input())
arr = sorted(list(map(int, input().split())))

# 초기값을 무한대로 설정
min_sum = float('inf')
result = []

# i는 첫 번째 용액을 선택하는 인덱스
for i in range(n - 2):
    s, e = i + 1, n - 1
    
    while s < e:
        current_sum = arr[i] + arr[s] + arr[e]
        
        # 현재의 합이 0에 더 가까운지 확인
        if abs(current_sum) < abs(min_sum):
            min_sum = current_sum
            result = [arr[i], arr[s], arr[e]]
        
        # 합이 0보다 크면 오른쪽 포인터를 줄여서 합을 줄입니다.
        if current_sum > 0:
            e -= 1
        # 합이 0보다 작으면 왼쪽 포인터를 늘려서 합을 증가시킵니다.
        elif current_sum < 0:
            s += 1
        # 합이 0이면 결과를 출력하고 종료합니다.
        else:
            print(arr[i], arr[s], arr[e])
            exit(0)

# 최종 결과 출력
print(*result)