[BOJ_20366] 같이 눈사람 만들래?

설명

---

2가지의 경우의 수를 먼저 고르고 O(N*N) 그리고 이때 투 포인터로 하나의 경우를 더 찾는 로직으로 눈사람을 설치 할 수 있다.

 

처음에 for문으로 투 포인터 방식을 생각하다가 잘 못 짜서 S는 무조건 상승하는 방식의 로직으로 구성해서 틀렸습니다가 많이 떴다. 생각해보면 S의 경우도 당연히 조건에 따라서 움직여야 하는데 생각이 얕아 고생을 했던 문제

 

총 시간 복잡도 : O(N^3)

 

 

코드

---

 

 

package two_pointer;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class BOJ_20366 {
    static int ans = Integer.MAX_VALUE;
    static List<Integer> snowList;
    public static void main(String[] args) throws Exception{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(in.readLine());
        snowList = new ArrayList<Integer>();
        StringTokenizer tk = new StringTokenizer(in.readLine()," ");

        for (int i = 0; i < N; i++){
            snowList.add(Integer.parseInt(tk.nextToken()));
        }
        Collections.sort(snowList);
        solve(N);
        System.out.println(ans);
    }

    private static void solve(int N) {
        int A = 0;
        int B = 0;
        int S = 0;
        int E = 0;
        for (int i = 0; i < N; i++){
            A = i;
            for (int j = i + 1; j < N; j++){
                S = 0;
                B = j;
                E = N - 1;
                while(S < E){
                    if(S == A || S == B){
                        S++;
                        continue;
                    }
                    if(E == A || E == B){
                        E--;
                        continue;
                    }
                    ans = Math.min(ans, Math.abs((snowList.get(A) + snowList.get(B)) - (snowList.get(S) + snowList.get(E))));
                    if((snowList.get(A) + snowList.get(B)) < (snowList.get(S) + snowList.get(E))) {
                        E--;
                    }
                    else{
                        S++;
                    }
                }
            }
        }
    }
}

20366번: 같이 눈사람 만들래?