[백준 BOJ / Python] 2473번 세 용액

문제

주어진 용액들 중에서 세 개를 선택해 특성 값의 합이 0에 가까운 조합을 찾는 문제이다.

풀이

• 정렬과 투 포인터 기법을 활용해 문제를 풀 수 있다.
• 먼저 주어진 용액들의 정보를 오름차순으로 정렬하면 더 효율적으로 조합을 찾을 수 있다.

• 세 개의 용액 중 한개를 임의로 고정하고 나머지 두 용액을 투 포인터로  탐색한다.
  • 첫번째 포인터(left)는 고정된 용액 바로 다음 위치를 가리킨다.
  • 두번째 포인터(right)는 정렬된 배열의 최대값인 오른쪽 끝을 가리킨다.
  • 세 원소의 합이 0보다 크면 오른쪽 포인터를 왼쪽으로 이동시켜 더 작은 값을 선택하게 한다.
  • 합이 0보다 작으면 왼쪽 포인터를 오른쪽으로 이동시켜 더 큰 값을 선택하게 한다.
  • 만약 0과 같으면 해당 조합이 최고의 조합임으로 해당 조합을 저장하고 탐색을 종료할 수 있다.

• 0과 가장 가까운 합을 찾을 때마다 해당 조합을 저장하고 반복한다.
• 이때 합에 절대값을 씌워 0과 가장 가까운 조합을 찾는다.

Python 코드

import sys
input = sys.stdin.readline
n = int(input())
arr = list(map(int, input().split()))
arr.sort() # 정렬하기
close2zero = float("INF") # 0과 가장 가까운 합을 저장해 놓을 변수
res = []   # 최고의 조합을 담을 리스트

for k in range(n-2): # 임의의 용액을 고정
    left, right = k+1, n-1 # 선택된 용액 이후의 최소값 최대값 위치

    while left < right < n:
        curSum = arr[k] + arr[left] + arr[right]

        # 현재 합이 0에 더 가까운 경우 업데이트
        if abs(curSum) < abs(close2zero):
            close2zero = abs(curSum)
            res = [arr[k], arr[left], arr[right]]

        # 0이면 최고의 조합임으로 탐색 종료
        if curSum == 0:
            print(*res)
            exit()
        elif curSum > 0: # 합이 0보다 크면 오른쪽 포인터를 왼쪽으로 이동
            right -= 1
        else: # 합이 0보다 작으면 왼쪽 포인터를 오른쪽으로 이동
            left += 1

print(*res)

 

문제출처

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