문제 링크: https://www.acmicpc.net/problem/2473

Thumbnail: Photo by Whitney Wright (Unsplash)

투 포인터에 이분 탐색을 응용하는 문제입니다.

풀이

기본적인 접근은 용액 (BOJ 2467)과 유사합니다. 2467번 문제에서는 투 포인터로 두 용액을 골랐다면, 이번에는 세 용액을 골라야 합니다.

다만, 문제에서 주어지는 용액의 개수 \(N\)의 범위는 \(3 < N < 5,000\)이므로 비교적 여유로운 편입니다. 따라서, 용액 하나를 기준으로 잡고 나머지 두 용액을 투 포인터로 적절히 탐색하는 방식을 사용했습니다.

입력 배열은 정렬되지 않은 상태로 주어지는데, 투 포인터 풀이에 사용하기 위해서 정렬해야 합니다.

투 포인터

기본적인 구성은 2개의 용액을 고르는 경우와 동일하지만, 용액을 세 개 골라야 하므로 기준점이 될 첫 용액은 \(1 \cdots N-2\)까지 모든 경우를 탐색합니다.

이후, 첫 용액 \(l\)에 대해 두 번째 용액 \(m\)을 \(l + 1\)로, 세 번째 용액 \(r\)을 \(N-1\)로 결정했습니다. 이는 같은 용액을 중복해서 사용할 수 없기 때문입니다.
\(l, m, r\)은 모두 입력 배열의 인덱스입니다.

\(m\)과 \(r\)의 두 포인터를 옮기는 조건은 다음과 같습니다:

• 현재 세 용액의 농도 합이 양수라면,
  • \(r\)을 1 감소시킵니다.
  • 입력 배열이 정렬된 상태이므로, \(N-1\)번 인덱스에 가까운 용액들은 전체 용액 중 농도가 큰 편에 속합니다. 농도 합의 절댓값을 줄이기 위해서는 기존보다 더 작은 수를 더해 총합이 작아지게 (0에 가까워지게) 해야 하므로, 기존 \(r\)보다 작은 수를 골라야 합니다.
• 현재 세 용액의 농도 합이 음수라면,
  • \(m\)을 1 증가시킵니다.
  • 입력 배열이 정렬된 상태이므로, 0번 인덱스에 가까운 용액들은 전체 용액 중 농도가 작은 편에 속합니다. 농도 합의 절댓값을 줄이기 위해서는 기존보다 더 큰 수를 더해 총합이 커지게 (0에 가까워지게) 해야 하므로, 기존 \(m\)보다 큰 수를 골라야 합니다.

for l in range(N - 2):
    m = l + 1
    r = N - 1
    while l < m and m < r  and r < N:
        cur_value = liquids[l] + liquids[m] + liquids[r]
        
        if abs(cur_value) < min_value: # 최솟값 정보 갱신
            min_value = abs(cur_value)
            min_pair[0] = liquids[l]
            min_pair[1] = liquids[m]
            min_pair[2] = liquids[r]
        
        # 포인터 옮길 조건
        if cur_value > 0:
            r -= 1
        elif cur_value < 0:
            m += 1
        else:
            break

전체 코드

input = open(0).readline
N = int(input())
liquids = sorted(map(int, input().split())) # 입력 배열을 정렬해서 받아야 한다.

if N == 3: # 탐색할 필요가 없는 경우
    print(*liquids)
    exit(0)

l = 0
r = N - 1
min_value = 1_000_000_000_001
min_pair = [None, None, None] # 최솟값인 경우의 세 용액을 저장할 배열
for l in range(N - 2):
    m = l + 1
    r = N - 1
    while l < m and m < r  and r < N:
        cur_value = liquids[l] + liquids[m] + liquids[r]
        
        if abs(cur_value) < min_value: # 최솟값 정보 갱신
            min_value = abs(cur_value)
            min_pair[0] = liquids[l]
            min_pair[1] = liquids[m]
            min_pair[2] = liquids[r]
        
        # 포인터 옮길 조건
        if cur_value > 0:
            r -= 1
        elif cur_value < 0:
            m += 1
        else:
            break     

print(*min_pair)