문제 이해

두 용액 문제와 비슷하다.
단지 이번엔 3개의 수를 뽑아서, 그 합의 절댓값을 가장 0에 가깝게 하고 싶다.

이 때, 합의 절댓값이 가장 0에 가까운 3 용액을 골라 오름차순으로 출력하는 것이 문제이다.

---

문제 풀이

두 용액 문제 + 좋다 문제를 합쳐서 생각했다.

A[i]를 먼저 선택한다.
A[i]는 항상 A[i+1] ~ A[배열의 끝]의 값과 더해질 수 밖에 없다.
즉, left = i+1, right = 배열의 끝 값을 가진다.

두 용액 문제와 비슷하게 처음으로 3 수의 합이 양수에서 음수로 변하는 그 타이밍을 살펴보는 방식으로 해결했다.

---

코드

import java.io.*;
import java.util.*;

public class Main {
	
	static int N;
	static Long[] A;
	static long ans_left = 0;
	static long ans_right = 0;
	static long ans_index = 0;
	static Long ans = Long.MAX_VALUE;
	
	static void two_pointer() {
		for(int i =0;i<N-2;i++) {
			long value = A[i];
			int left = i+1;
			int right = N-1;
			
			search(left,right,value);
            /*
            A[i] + A[left] + A[right] 중 가장 0에 가까운 값을 구하는 메서드
            left = i+1, right = N-1로써 right은 왼쪽으로만, 
            left는 오른쪽으로만 이동한다.
            */
		}
		
		StringBuilder sb = new StringBuilder();
		sb.append(ans_left).append(" ").append(ans_right).append(" ")
        											.append(ans_index);
		
		System.out.println(sb);
	}
	
	static void search(int left, int right, Long value) {
		while(left < right) {
			long sum = A[left] + A[right] + value;
			
			if(Math.abs(sum)<ans) {
            // 이전에 저장되어 있던 3 용액의 합보다 작으면 이번에 입력받은 
            // left, right을 새로 저장
				ans_left = value;
				ans_right = A[left];
				ans_index = A[right];
				ans = Math.abs(sum);
			}
			
			if(sum>=0) {
            /*
            A[left] + A[right]에서 A[right]는 감소만 하고, 
            A[left]는 증가만 할 수 있다.
            
            이는 Sorting과 left, right포인터의 이동 방향이 정해져 있기 때문이다
            만약 sum이 양수라면 sum을 작게 해야 하므로, 
            right을 왼쪽으로 이동시켜 A[right]을 감소시킨다.
            */
				right--;
			}
			else {
                // A[left] + A[right]가 음수가 되었다.
                // 다시 양수를 만들고 싶기 때문에 증가 시켜야 하고, 
                // 따라서 left를 오른쪽으로 이동 시킨다.
				left++;
			}
		}
	}
	
	public static void main(String[] args) {

		FastReader sc = new FastReader();

		N = sc.nextInt();
		A = new Long[N];
		for(int i =0;i<N;i++) {
			A[i] = sc.nextLong();
		}
		Arrays.sort(A); // 이 알고리즘의 핵심. Sorting!!
		
		two_pointer();
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과

• 2번째 줄 시간 초과 : binary search를 통해 문제를 해결하려고 하였는데, if-else 구문이 너무 많아 분기가 너무 많아졌다. 하지만, 핵심적인 문제는 실수로 binary search 이후 값을 통해 left와 right을 너무 복잡하게 이동시켜 추가적인 계산이 너무 많아져 쓸모 없는 계산이 증가하였다.