bj20366(같이 눈사람 만들래?)-투 포인터

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

이 문제는 투 포인터 시간 복잡도 계산을 잘 해야하는 문제였다.

600개의 눈덩이가 있을때,

엘자보다 안나의 눈사람이 무조건 작다고 가정한다.

엘자가 만들 수 있는 모든 눈사람의 높이를 구한 후(601 * 300 = 180000)

안나의 눈사람을 투 포인터로 만든다.(600)

즉, 108000000 으로 1초 조금 넘는 시간복잡도를 갖는다.

투 포인터는 최대/최솟값과 같은 조건에 가까운 두 개의 값을 구할 때 사용한다는 것을 배웠다.

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

public class Main {
    static int N;
    static int[] nums;
    static StringTokenizer stringTokenizer;
    static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        initialize();
        System.out.println(solve());
    }

    private static int solve() {
        int answer = Integer.MAX_VALUE;

        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                int elza = nums[i] + nums[j];
                answer = Math.min(answer, twoPointer(i, j, elza));
            }
        }

        return answer;
    }

    private static int twoPointer(int i, int j, int elza) {
        int min = Integer.MAX_VALUE;
        int start = 0;
        int end = N - 1;

        while (start < end) {
            if (start == i || start == j) {
                start++;
                continue;
            }
            if (end == i || end == j) {
                end--;
                continue;
            }
            int diff = Math.abs(elza - (nums[start] + nums[end]));
            min = Math.min(min, diff);
            if (nums[start] + nums[end] < elza) {
                start++;
            } else {
                end--;
            }
        }

        return min;
    }

    private static void initialize() throws IOException {
        N = Integer.parseInt(bufferedReader.readLine());
        nums = new int[N];
        stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        for (int i = 0; i < N; i++) {
            nums[i] = Integer.parseInt(stringTokenizer.nextToken());
        }
        Arrays.sort(nums);
    }
}