[BOJ 2473] 세 용액 (Java, 투 포인터)

 

 

---

문제 링크

https://www.acmicpc.net/problem/2473

2473번: 세 용액

---

풀이

- 정렬 후 투 포인터 로직 수행

- 시간 복잡도 : O(NlogN) 

- 배열 순차적으로 순회하여 기준 값과 나머지 영역에서 투 포인터로 두 값을 정하고 다 더했을 때 0에 가까운 최대 값을 구하면 됨

 

참고

[BOJ 2470] 두용액 (Java, 투 포인터)

[BOJ 1253] 좋다 (Java, 투 포인터) 

---

제출 코드 

- 입력 배열 A 의 데이터 타입을 long으로 해야 함 (int로 하여 틀린 원인 찾지 못하여 시간 소모)

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

public class Main {
    static StringBuilder sb = new StringBuilder();

    static int N;

    static long BEST, V1, V2, V3;
    static long[] A;

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());

        A = new long[N + 1]; // int 실수*
        st = new StringTokenizer(br.readLine());
        for(int i = 1; i <= N; i++) {
            A[i] = Long.parseLong(st.nextToken());
        }

        BEST = Long.MAX_VALUE;
    }

    static void twoPoint(int baseIdx) {
        int L = baseIdx + 1, R = N;
        while(L < R) {
            long sum = A[baseIdx] + A[L] + A[R];

            if(Math.abs(sum) < BEST) {
                BEST = Math.abs(sum);
                V1 = A[baseIdx];
                V2 = A[L];
                V3 = A[R];
            }

            if(sum > 0) R -= 1;
            else L += 1;
        }
    }

    static void pro() {
        Arrays.sort(A, 1, N + 1);

        for(int i = 1; i <= N - 2; i++) { // 세 용액이니 종료 범위 조정
            twoPoint(i);
        }

        sb.append(V1).append(" ").append(V2).append(" ").append(V3);
        System.out.println(sb);
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }

}