[BOJ] 백준 2473번 문제 풀이 (Python)

1. 문제 풀이

two pointer를 사용한 3SUM 알고리즘을 이용하여 풀었다.

• two pointer를 사용하기 위해 먼저 정렬한다.
• 첫번째 숫자부터 숫자를 하나씩 고정시킨 후, 나머지 숫자들에 two pointer 알고리즘을 적용하여 세 수의 합(고정된 숫자+왼쪽 포인터 숫자+오른쪽 포인터 숫자)을 찾아낸다.
  • 세 수의 합이 0이랑 같은 경우: 원하던 합이므로 숫자들을 반환한다.
  • 세 수의 합이 0보다 큰 경우: 오른쪽 포인터를 왼쪽으로 한 칸 옮긴다.
  • 세 수의 합이 0보다 작은 경우: 왼쪽 포인터를 오른쪽으로 한 칸 옮긴다.
  • 입력으로 들어온 숫자가 모두 양수라면 가장 작은 세 수의 합이 정답이고 모두 음수라면 가장 큰 세 수의 합이 정답이기 때문에 입력으로 들어온 숫자가 꼭 음수, 양수 조합이 아니더라도 해당 알고리즘이 적용된다.

2. 코드

import sys
def input(): return sys.stdin.readline().rstrip()

def find_value(n, nums):
    result = [1e9,1e9,1e9]
    for i in range(n):
        l, r = i+1, n-1
        while l < r:
            # 세 수의 합이 0이 되는 것이 없을 경우를 대비해 0과 가장 가까운 세 수의 합을 찾아낸다.
            if abs(sum(result)) > abs(nums[i] + nums[l] + nums[r]):
                result = [nums[i], nums[l], nums[r]]

            if nums[i] + nums[l] + nums[r] == 0:
                return nums[i], nums[l], nums[r]
            elif nums[i] + nums[l] + nums[r] > 0:
                r -= 1
            else:
                l += 1
    return result[0], result[1], result[2]

n = int(input())
nums = list(map(int,input().split()))
nums.sort()

print(*find_value(n,nums))