Q. 20366 자바 : 같이 눈사람 만들래?

 

문제 :boj.kr/20366

골드 3 난이도의 문제이다.

투 포인터 강의를 듣고나서, 투 포인터 유형의 다른 문제들을 찾아보다가 발견한 문제이다.

 

처음에 문제를 봤을 때는 어떻게 접근해야 할 지 감이 안잡혔었는데,

감이 안잡혀서 검색을 했더니, 세 용액 문제와 비슷한, 네 용액 문제로 풀면 된다는 내용이 있길래

그 내용만 보고 추측해서 풀었더니 다행히 풀렸다.(다른 블로그 코드 참고x)

 

 

문제를 보면 하나의 눈사람은 두 개의 눈덩이로 구성되고 눈덩이가 주어지면,

두 눈사람의 키 차이가 가장 작은 값을 구하라는 문제이다.

---

1. 투 포인터 알고리즘을 이용해 값을 조정하려면,

눈덩이들이 정렬된 상태여야 하므로 먼저 정렬을 해준다. - O(N log N) 

2. 네 개의 값을 뽑아야 하므로 먼저 두 개의 값을 선택하고- O(N^2)

이후에  다른 두 값을 투 포인터 알고리즘을 사용해 키 차이가 가장 작아지도록 구한다 - O(N)

(이 때 네개의 값이 모두 다른 눈덩이를 선택해야 하므로 같은 눈덩이일 경우를 생각해야 한다.)

3. 두 눈사람의 키 차이가 가장 작은 값 이므로 절댓값이 0에 가장 가까운 값이 이 문제에서 원하는 값이고, 

위의 방식을  사용해서 정답을 계산한다.

 

그래서 내가 푼 코드의 시간 복잡도는 N logN + N^2 + N 이므로 약 O(N^2)의 시간복잡도를 가지고,

이 문제의 입력 조건을 확인하면 N의 최대값이 600이므로 시간초과가 나지 않을것을 예상할 수 있다.

 

주의해야 할 자료형은 눈덩이의 지름 H의 최대값이 10^9이므로 이 값들은 int 범위를 벗어나지 않고,

네 눈덩이의 합 역시 int 범위 내에서 처리가 가능하다. (세 용액 문제는 Long을 이용해야 했다)

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

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

    static int N, v1, v2, v3, v4;
    static int best_sum = Integer.MAX_VALUE;
    static int[] A;

    static void input() {
        N = scan.nextInt();
        A = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            A[i] = scan.nextInt();
        }
    }
    static void func(int idx1, int idx2) {
        
        int L = 1, R = N;
        int cur = A[idx1] + A[idx2];
        while (L < R) {
            if (L == idx1 || L == idx2) {
                L++;
                continue;
            }
            if (R == idx1 || R == idx2) {
                R--;
                continue;
            }

            int sum = A[L] + A[R] - cur;
            if (Math.abs(sum) < best_sum){
                best_sum = Math.abs(sum);
            }
            if (A[L] + A[R] > cur) R--;
            else L++;
        }
    }
    static void pro() {

        Arrays.sort(A, 1, N + 1);
        for (int i = 1; i < N; i++) {
            for (int j = i + 1; j <= N; j++) {
                func(i, j);
            }
        }

        System.out.println(best_sum);
    }

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


    static class FastReader { 
        // BufferedReader의 빠른 속도, 
        // + Scanner의 타입별 입력값을 받는 기능을 혼합
        // (자바 내부에 구현된 Scanner는 속도가 느림)
        // 다른분의 코드를 참고한 코드
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}