[백준] 20366번: 같이 눈사람 만들래?-JAVA

문제 바로 가기 > 백준 20366번: 같이 눈사람 만들래?

 

정렬을 이용해 푸는 문제이다.

 

처음에는 아래와 같이 4중 for문을 이용해 풀려고 했으나 이렇게 풀면 N(4 ≤N≤ 600) 이여서 시간 초과가 난다.

1. 엘사가 만든 눈사람의 몸통 선택 → O(N)
2. 엘사가 만든 눈사람의 머리 선택 → O(N)
3. 안나가 만든 눈사람의 몸통 선택 → O(N)
4. 안나가 만든 눈사람의 머리 선택 → O(N)
   1. 엘사가 만든 눈사람과 안나가 만든 눈사람의 키차이를 구하고 최소 비교

➡️ 해당 풀이법의 시간 복잡도 : O(N4) → 시간 초과

 

그래서 몸통+머리를 합쳐서 눈사람을 우선 만들어서 정렬한 후에 이 눈사람의 뒷값과 비교를 한다.
핵심은 정렬을 했기 때문에 현재 눈사람과의 차이가 가장 작은 눈사람은 내 바로 뒤의 인덱스에 있는 눈사람이라는 것이다.

1. 만들 수 있는 모든 눈사람의 조합을 (몸통+머리) 계산 → O(N2)
2. 눈사람의 키에 대해 따라 정렬 → O(N2)
3. i 번째 눈사람와 i + 1번째 눈사람의 차이가 가장 작을때 두 눈사람의 키차이가 최소일때 → O(logN)

➡️ 해당 풀이법의 시간 복잡도 : O(N2)

 

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

public class _20366 {
    public static void main(String[] args)throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());
        int n=Integer.parseInt(st.nextToken());
        int[] snow=new int[n];
        st=new StringTokenizer(br.readLine());
        for(int i=0;i<n;i++){
            snow[i]=Integer.parseInt(st.nextToken());
        }

        ArrayList<SnowMan> snowMans=new ArrayList<>();
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                snowMans.add(new SnowMan(i,j,snow[i]+snow[j]));
            }
        }
        int min=Integer.MAX_VALUE;
        Collections.sort(snowMans);
        for(int i=0;i<snowMans.size()-1;i++){
            int firstHIdx=snowMans.get(i).headIdx;
            int firstBIdx=snowMans.get(i).bodyIdx;
            int secondHIdx=snowMans.get(i+1).headIdx;
            int secondBIdx=snowMans.get(i+1).bodyIdx;
            if(firstHIdx!=secondHIdx&&firstHIdx!=secondBIdx&&firstBIdx!=secondHIdx&&firstBIdx!=secondBIdx){
                min=Math.min(min, Math.abs(snowMans.get(i+1).height-snowMans.get(i).height));
            }
        }
        System.out.println(min);

    }
    public static class SnowMan implements Comparable<SnowMan>{
        public int headIdx;
        public int bodyIdx;
        public int height;

        public SnowMan(int headIdx, int bodyIdx, int height){
            this.headIdx=headIdx;
            this.bodyIdx=bodyIdx;
            this.height=height;
        }

        @Override
        public int compareTo(SnowMan o){
            return this.height-o.height;
        }
    }
}