• 출처 : https://www.acmicpc.net/problem/2473

• 알고리즘 : 정렬, 투 포인터

• 풀이

  1. n = 5000 → O(n^2) 까지 가능 (파이썬)
  2. 정렬
  3. 각 원소 순회 → O(n)
  4. 현재 원소를 제외한 나머지 배열에 대해 투 포인터 알고리즘을 통해 절댓값의 최솟값 찾기

• 투 포인터 알고리즘 구현

  1. deque를 사용해 양 끝을 pop
  2. 합이 0보다 크면 pop
  3. 합이 0보다 작으면 popleft
  4. 중간중간 절댓값의 최솟값과 비교 반복

• 소감

  • 풀이 검색..
  • 어렵다

코드

# 투 포인터

from collections import deque

def init():

    n = int(input(''))
    num_list = list(map(int, input('').split(' ')))

    return n, num_list

n, num_list = init()

num_list.sort()

min_value = float('inf')
min_combi = [float('inf'), float('inf'), float('inf')]

finished = False
for i in range(n-2):
    
    start_value = num_list[i]
    q = deque(num_list[i+1:])

    left = q.popleft()
    right = q.pop()

    while True:

        temp_combi = [start_value, left, right]
        temp_value = abs(sum(temp_combi))

        if temp_value < min_value:
            min_combi = temp_combi
            min_value = temp_value

        if len(q) == 0:
            break

        if start_value + left + right == 0:
            finished = True
            break

        elif start_value + left + right > 0:
            right = q.pop()

        elif start_value + left + right < 0:
            left = q.popleft()

    if finished:
        break

min_combi.sort()
for i in range(3):
    print(min_combi[i], end=' ')