[자바] 백준 2473 - 세 용액 (java)

목차

문제 : boj2473

 

 

필요 알고리즘

• 투 포인터 또는 이분 탐색
  
  • 투 포인터를 쓰거나, 이분 탐색을 써서 풀 수 있는 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  우선 처음 생각난 아이디어는, 어차피 n이 5000이므로 2개를 고정시켜놓고, 나머지 하나의 값을 이분 탐색으로 찾는 방법이었다. 이 경우 O(N^2 * logN). 예를들어 현재 고정시켜둔 2개의 값이 -97와 -2라면, -(-97-2) = 99 이므로 최대한 99랑 비슷한 값을 이분탐색으로 찾는거다. 정확히 해당 값이 아니라, 그 근처의 값을 찾아야하니 99보다 큰 값과 99보다 작은 값 모두 찾아야하고 이전에 고정해둔 2개의 인덱스값과도 일치하지 않아야하니 상당히 구현하기가 귀찮다.

 

  사실 어제 이분 탐색으로 풀려고 했는데 자꾸 맞왜틀을 외치다가 그냥 패스했고, 오늘 아침에 '아 걍 투포인터로 하면 되는데;;' 생각나서 다시 풀어서 몇분만에 바로 맞췄다 ㅋㅋ. 이론상 이분 탐색으로 푸는데 전혀 문제가 없고 그냥 내가 구현을 실수한거겠고, 이분 탐색으로 시간초과도 안 뜰 시간복잡도다보니 투 포인터라는 더 쉽고 효율적인 방법이 있는데도 다른 방법을 어제 바로 생각하지 못하게 됐던 것 같다. 이후엔 주의해야할 것 같다.

 

  아무튼 투 포인터를 사용한 풀이는 1개를 고정시켜두고 나머지 2개를 투 포인터로 찾는 방법이다. 이 경우 O(N^2). 시간상으로도 이득이고, 구현도 훨씬 간편하다. 투 포인터 알고리즘을 알고 있다면 이하 주석만 보면 풀이는 알 수 있을꺼라 생각된다.

for (int base = 0; base < n; base++) {	// 하나의 값을 고정해두고
    int s = 0;	// 투 포인터를 진행한다. 물론 arr[]은 이미 정렬된 상태다.
    int e = n-1;

    while (s<e) {
        if (s == base) {s++; continue;}	// 고정해둔값과 동일하면 안된다.
        if (e == base) {e--; continue;}

        long sum = 0l + arr[base] + arr[s] + arr[e];
        if (Math.abs(sum) < min) {	// 현재까지 찾은 최소값보다 합이 더 작다면
            min = Math.abs(sum);	// 답을 교체한다.
            ans = new int[] {arr[base], arr[s], arr[e]};
        }

        if (sum == 0) {printAns(ans); return;}	// 0은 최소치라 더이상 다른걸 찾아볼 이유가 없다.
        if (sum < 0) {s++; continue;}	// 합이 0 미만이면 합을 더 증가시켜야하니 s++
        e--;	// 0 초과라면 합을 더 감소시켜야하니 e--
    }
}

printAns(ans);

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1 << 16);

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr);
        long min = Long.MAX_VALUE;
        int[] ans = new int[3];

        for (int base = 0; base < n; base++) {
            int s = 0;
            int e = n-1;

            while (s<e) {
                if (s == base) {s++; continue;}
                if (e == base) {e--; continue;}

                long sum = 0l + arr[base] + arr[s] + arr[e];
                if (Math.abs(sum) < min) {
                    min = Math.abs(sum);
                    ans = new int[] {arr[base], arr[s], arr[e]};
                }

                if (sum == 0) {printAns(ans); return;}
                if (sum < 0) {s++; continue;}
                e--;
            }
        }

        printAns(ans);
    }

    private void printAns(int[] ans) {
        Arrays.sort(ans);
        System.out.println(ans[0] + " " + ans[1] + " " + ans[2]);
    }
}