[Python] 2467 - 용액

[Gold V] 용액 - 2467 

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

🗝️알고리즘 분류

• 두 포인터
• 이분 탐색

---

💻문제 정의

주어진 용액들 중에서, 두 용액을 섞었을 때 그 합이 0에 가깝도록 하는 두 용액을 찾아내는 프로그램을 만드는 문제이다.

 

💡접근 및 설계

두 포인터와 이분 탐색을 활용하여 알고리즘을 설계하였다. 용액을 크기별로 정렬하여 가장 큰 용액과 가장 작은 용액의 합을 구한다. 이후 이 합을 기준으로 start와 end 값을 조절하여 0에 가깝게 하는 용액을 찾아간다.

 

✏️알고리즘 풀이

start, end = 0, N-1

answer = abs(liquid[start] + liquid[end]) # 두 용액의 합
result = [liquid[start], liquid[end]] # 두 용액 저장 리스트

while (start < end):
    min = liquid[start] # 가장 작은 용액
    max = liquid[end] # 가장 큰 용액

    sum = min + max # 두 용액의 합

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

        if (answer == 0): # 합이 0이면 무조건 최솟값
            break

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

    else: # 합이 양수일 경우, 그 다음 큰 용액으로 변경
        end -= 1

start, end는 용액이 저장된 리스트의 인덱스가 된다.

answer는 선택된 두 용액의 합이고, result는 그 두 용액을 저장하는 리스트다.

 

이분 탐색을 통해 min, max의 합 sum과 answer를 비교하며 적절한 값을 찾아가도록 한다.

 

🗒️전체 코드

# 2467 용액

import sys
input = sys.stdin.readline

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

start, end = 0, N-1

answer = abs(liquid[start] + liquid[end]) # 두 용액의 합
result = [liquid[start], liquid[end]] # 두 용액 저장 리스트

while (start < end):
    min = liquid[start] # 가장 작은 용액
    max = liquid[end] # 가장 큰 용액

    sum = min + max # 두 용액의 합

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

        if (answer == 0): # 합이 0이면 무조건 최솟값
            break

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

    else: # 합이 양수일 경우, 그 다음 큰 용액으로 변경
        end -= 1

print(result[0], result[1])

---