[BOJ 2473, Python] 세 용액

문제 링크

BOJ 2473

분류

이분 탐색, 정렬, 두 포인터

설명

전형적인 투 포인터 문제에서 살짝 더 나간 문제인 거 같다.

처음에 이 문제를 풀 때 3개의 용액을 합쳐야 하는 것 때문에 뭔가 다른 풀이가 있을 것이라고 생각한 나머지 의외로 정공법을 사용하지 않았고 그러다보니 실제 풀이가 늦어지는 결과를 낳았다.

해당 문제에서 주의해서 봐야 할 부분은 전체 용액의 수가 5000 이하라는 점이다. 해당 조건이 없다면 이 문제를 절대 시간 내에 풀 수 없다... 처음에 이 조건을 유심히 보지 않아 다른 풀이법을 계속 찾게 된 점은 지금 봐도 아쉬운 점이었다.

따라서 이 문제의 해결 방법은 이렇게 제시해 볼 수 있겠다.

순서 정렬 → 용액 1개 고정 → 나머지 용액에 대해 해당 용액과 합하여 가장 0에 가까워 질 수 있도록 투포인터 알고리즘 사용 → 전부 순회했거나 0에 도달했다면 종료

풀이 코드

# 세 용액

import sys

input = sys.stdin.readline

solution_number = int(input())
solution_list = list(map(int, input().split()))

solution_list.sort()
characteristic_value = 3000000000

for idx in range(solution_number):

    pointer_1 = 0
    pointer_2 = solution_number - 1

    while pointer_1 < pointer_2:

        if pointer_1 == idx:
            pointer_1 += 1
        if pointer_2 == idx:
            pointer_2 -= 1

        if pointer_1 >= pointer_2:
            break

        now_value = sum([solution_list[idx], solution_list[pointer_1], solution_list[pointer_2]])

        if abs(now_value) < characteristic_value:
            characteristic_value = abs(now_value)
            result = [solution_list[idx], solution_list[pointer_1], solution_list[pointer_2]]

            if not characteristic_value:
                break

        if now_value < 0:
            pointer_1 += 1
        elif now_value > 0:
            pointer_2 -= 1

    if not characteristic_value:
        break

result.sort()

print(*result)