[백준] 2473번. 세 용액(JAVA)

문제

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

---

풀이

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

public class Main {

    static int n;
    static long[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        n = Integer.parseInt(br.readLine()); // 몇개의 용액이 들어오는지
        arr = new long[n]; // 용액의 값을 저장할 배열
        // int로 받아도 저장하는데는 문제가 없다.
        // 하지만, 세 용액을 더할 경우 정수 오버플로우 문제가 발생할 가능성이 있다.
        // 따라서 덧셈 시 캐스팅을 해줘도 되지만 그렇지 않고 받을 때 애초에 long 타입으로 받았다.

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++){
            arr[i] = Long.parseLong(st.nextToken()); // long타입을 받기 위함
        }

        Arrays.sort(arr);
        long ans = Long.MAX_VALUE;
        long[] ansArr = new long[4]; // 정답에 관한 값들을 저장할 배열
        // 인덱스 0: 세 용액의 합
        // 인덱스 1~3 : 인덱스 값
        for(int i = 0; i < n - 2; i++){
            long[] temp = twoPointer(i+1, n - 1, i);
            if(temp[0] < ans) {
                ans = temp[0];
                ansArr = Arrays.copyOf(temp, 4);
            }
        }

        System.out.println(ansArr[1] + " " + ansArr[2] + " " + ansArr[3]);
    }
    private static long[] twoPointer(int start, int end, int pointIdx){
        long[] returnArr = new long[4];
        long answer = Long.MAX_VALUE;
        while(start < end){
            long temp  = arr[start] + arr[end] + arr[pointIdx];
            if(answer > Math.abs(temp)){
                answer = Math.abs(temp);
                returnArr[0] = answer;
                returnArr[1] = arr[pointIdx];
                returnArr[2] = arr[start];
                returnArr[3] = arr[end];
            }
            if(temp == 0){
                returnArr[0] = 0;
                returnArr[1] = arr[pointIdx];
                returnArr[2] = arr[start];
                returnArr[3] = arr[end];
                return returnArr;
            }
            if(temp < 0){
                start++;
                continue;
            }
            if(temp > 0){
                end --;
            }
        }

        return returnArr;
    }


}

 

2467번 문제와 매우 유사하다. 다만 문제를 정확히 분석하는 습관을 들이기 위해 비교를 해보자.

1. 문제 자체가 다른 점은 두 가지 용액이 들어오던 것이 3가지 용액이 들어온다는 것이다.

2. 2467번의 경우 사용자 입력이 오름차순으로 들어오지만 2473번은 아니다. -> 투 포인터 알고리즘을 사용하려고 하는 경우 정렬이 필요할 것이다.

3. 2467번의 경우 용액입력이 100,000개까지 가능하지만 2473번은 5,000까지만 가능하다. -> 하나를 고정시킨 투포인터 알고리즘으로도 해결이 가능할 수 있다.

 

2467번이 투포인터인 이유는 무엇일까? 물론 하나를 고정해 두고 나머지를 전부 탐색하는 방법을 사용할 수 있다. 이 경우 n*(n-1)의 경우가 생기므로 O(N^2)이 된다. 즉, 100,000*100,000이라는 괴랄한 연산을 유발하게 된다. 즉, 1초에 1억 번의 계산을 하게 되는 일반적인 경우를 고려했을 때 문제를 해결할 수 없다.

 

투포인터를 사용하면 O(N)의 시간복잡도를 가지기 때문에 문제를 해결할 수 있는 것이다.

 

그럼 쓰리포인터는 없나??? -> 뭐 만들려면 만들 수야 있겠지만 이 문제의 경우 효율적인지? 가능한지? 에 대해 고민을 했다.

그러던 중 보인 것이 n이 5000까지만 가능하다는 것이다. 즉 투포인터인 O(N)에 의해 하나를 고정시켜도 5,000*5,000이라는 연산만 하면 된다는 소리이다. 이 경우 2500만번의 연산이면 문제를 해결할 수 있기에 가능했다. -> 마찬가지로 그냥 다 해보면 5,000*5,000*5,000이라 안 된다.