[BOJ] #2470 두 용액 (Python)

🌱 문제

2470번: 두 용액

 

 

🌱 풀이

이 문제는 투 포인터 알고리즘을 이용합니다. 투 포인터 알고리즘이란, 1차원 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해가면서 원하는 값을 구하는 알고리즘입니다.

 

1. 입력받기

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

입력은 두 줄이 주어집니다. 첫째 줄에는 전체 용액의 수인 n을 입력받고, 둘째 줄에서는 용액의 특성값들인 n개의 정수들을 리스트로 입력받습니다. 이때, 리스트는 정렬을 해주어야 합니다.

 

2. 변수 초기화

min = sys.maxsize
start = 0
end = n - 1
result = []

• min은 용액의 특성값의 합의 절댓값 중 최솟값을 담는 변수입니다. 투 포인터를 조작할 때마다 min값이 업데이트 될 수 있습니다.
• start와 end는 liquid 리스트의 두 원소를 가리키는 투 포인터에 해당합니다. liquid 리스트를 이미 정렬해주었으므로 양 쪽 끝에서 시작하여 범위를 줄여갑니다.
• result는 출력할 결과 값을 담는 리스트입니다. min이 업데이트될 때마다 result도 업데이트 됩니다.

 

3. 투 포인터 알고리즘으로 범위를 줄여가기

while start < end:
    mix = liquid[start] + liquid[end]

    if abs(mix) < min:
        min = abs(mix)
        result = [liquid[start], liquid[end]]

    if mix < 0:
        start += 1
    elif mix > 0:
        end -= 1
    else:
        break

• start와 end가 만나기 전까지 반복하며, 두 용액의 특성값의 합이 0이 되면 반복문을 즉시 종료합니다.
• mix는 두 용액의 특성값을 합한 값을 담고 있습니다.
• 우리의 목표는 mix의 절대값이 0과 가장 가깝도록 하는 두 용액을 선택하는 것이므로 mix의 절대값을 현재 min값과 비교하여 더 작다면 min과 result를 업데이트합니다.
• mix값이 음수라면 투 포인터 조작 시, start를 1 증가시켜 이후 계산될 mix값을 증가시켜 0에 가깝도록 합니다. 반대로 min값이 양수라면 투 포인터 조작 시, end를 1 감소시켜 mix값이 0에 가깝도록 합니다.
• mix값이 0이라면 더이상 개선할 사항이 없기 때문에 반복문을 종료합니다.

 

🌱 정답 코드

# !/usr/bin/env python
# -*- coding: utf-8 -*-
# boj 2460 두 용액

import sys

input = sys.stdin.readline

n = int(input())
liquid = list(map(int, input().split()))

min = sys.maxsize
liquid.sort()
start = 0
end = n - 1
result = []

while start < end:
    mix = liquid[start] + liquid[end]

    if abs(mix) < min:
        min = abs(mix)
        result = [liquid[start], liquid[end]]

    if mix < 0:
        start += 1
    elif mix > 0:
        end -= 1
    else:
        break

print(*result)