[Python] 2473 - 세 용액

[Gold III] 세 용액 - 2473 

[문제 링크](https://www.acmicpc.net/problem/2473)

🗝️알고리즘 분류

• 두 포인터
• 이분 탐색

---

💻문제 정의

용액의 리스트가 주어지면, 용액의 합이 0에 가깝도록 하는 세 용액을 출력하는 문제이다.

 

💡접근 및 설계

이전에 두 용액이라는 문제를 풀었을 때, 이분 탐색을 활용하여 두 용액의 합을 비교하며 두 개의 용액을 찾아 문제를 해결하였다.

이번 세 용액 문제는 하나의 용액을 고정하고, 고정한 용액을 제외한 용액들 중에서 이분 탐색을 통해 두 용액을 찾는 방식으로 문제를 해결하였다.

 

✏️알고리즘 풀이

for i in range(N-2):
    start = i+1
    end = N-1

    while (start < end):
        fix = liquid[i] # 용액 고정
        min = liquid[start] # 고정 용액을 제외한 가장 작은 용액
        max = liquid[end] # 고정 용액을 제외한 가장 큰 용액

        sum = fix + min + max # 용액 합

        if (abs(sum) < answer):
            answer = abs(sum)
            result = [liquid[i], min, max]

        if (sum < 0): # 합이 음수일 경우, 그 다음 작은 용액으로 변경
            start += 1

        elif (sum > 0): # 합이 양수일 경우, 그 다음 큰 용액으로 변경
            end -= 1
        
        else: # 합이 0일 경우, 가장 작은 경우
            break

fix를 선언하고, fix를 기준으로 큰 용액들에 대해서 이분 탐색으로 두 용액을 찾아낸다.

fix를 변경하여 다시 이분 탐색을 진행하는 과정을 반복하여 최소 sum을 찾는다.

 

🗒️제출 코드

# 2473 세 용액

import sys
input = sys.stdin.readline

N = int(input())
liquid = list(map(int, input().split()))
liquid.sort()

answer = sys.maxsize

for i in range(N-2):
    start = i+1
    end = N-1

    while (start < end):
        fix = liquid[i] # 용액 고정
        min = liquid[start] # 고정 용액을 제외한 가장 작은 용액
        max = liquid[end] # 고정 용액을 제외한 가장 큰 용액

        sum = fix + min + max # 용액 합

        if (abs(sum) < answer):
            answer = abs(sum)
            result = [liquid[i], min, max]

        if (sum < 0): # 합이 음수일 경우, 그 다음 작은 용액으로 변경
            start += 1

        elif (sum > 0): # 합이 양수일 경우, 그 다음 큰 용액으로 변경
            end -= 1
        
        else: # 합이 0일 경우, 가장 작은 경우
            break

for ix in result:
    print(ix, end = ' ')

---