[BOJ] #2473 세 용액 (Python)

🌱 문제

2473번: 세 용액

 

🌱 풀이

[BOJ] #2470 두 용액 (python)

2470번 두 용액의 업그레이드 버전입니다. 문제는 같고 용액만 3개를 고르면 됩니다. 포인터가 추가적으로 하나 더 필요한데, 용액의 개수가 3부터 5000으로 그리 크지 않습니다. 그래서 for문으로 

 

1. 입력받기

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

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

 

2. 변수 초기화

result = []
min = sys.maxsize

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

 

3. 하나 고정 + 투 포인터

for i in range(n - 2):
    start = i + 1
    end = n - 1
    while start < end:
        mix = liquid[i] + liquid[start] + liquid[end]
        if abs(mix) < min:
            min = abs(mix)
            result = [liquid[i], liquid[start], liquid[end]]

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

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

 

🌱 정답 코드

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

import sys

input = sys.stdin.readline

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

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

for i in range(n - 2):
    start = i + 1
    end = n - 1
    while start < end:
        mix = liquid[i] + liquid[start] + liquid[end]
        if abs(mix) < min:
            min = abs(mix)
            result = [liquid[i], liquid[start], liquid[end]]

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

print(*result)

 

위 코드를 python3으로 제출하면 시간 초과가 나옵니다😅 PyPy3로 제출했을 때는 시간 초과 없이 정답이 됩니다!