[BOJ 2473, Python] Tax Solutions

Problem link

boj 2473

Classification

Bisection, sorting, two pointers

Description

This is a slightly more advanced version of the classic two-pointer problem.

When I first solved this problem, I thought there must be a different solution because I had to combine the three solutions, so I surprisingly didn't use the exact method, which slowed down the actual solution.

The important thing to note about this problem is that the total number of solutions is 5000 or less. Without this condition, this problem would never be solved in time... I'm glad I didn't pay attention to this condition in the beginning, as it led me to keep looking for other solutions.

So, the solution to this problem is as follows.

Sort the order → fix one solution → use a two-pointer algorithm for the remaining solutions to sum with that solution to get closest to zero → stop when all have been traversed or when zero is reached

Solving code

# 세 용액

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)