[JAVA] 백준 20366번 【G3.같이 눈사람 만들래?】

문제

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

---

풀이

 

1️⃣ 조합을 이용한 풀이

주어진 눈덩이 중 2개로 만들 수 있는 눈사람의 높이를 모두 구한다.

 

단, 두 사람이 같은 눈덩이를 사용할 수 없다. 서로 다른 눈덩이 4개가 사용되어야 한다.

 

따라서, 그냥 합의 조합만 구하면 이러한 부분을 체크할 수 없기 때문에 어떤 인덱스의 눈덩이로 눈사람을 만든건지 정보가 필요하다.

 

따라서, 클래스를 새롭게 하나 정의해야한다.

 

    static class SnowMan{
        int idx1;
        int idx2;
        int height;
        public SnowMan(int idx1, int idx2, int height) {
            this.idx1 = idx1;
            this.idx2 = idx2;
            this.height = height;
        }
    }

 

위와 같은 SnowMan 클래스를 정의한다.

 

어떤 인덱스의 눈덩이를 사용해서 만들었는지, 총 높이는 얼마인지를 보관할 수 있다.

 

이제, 눈사람 조합을 List 에 넣고 눈사람 높이를 기준으로 정렬한다.

 

그 이유는, 문제에서 요구하는 건 두 눈사람의 높이의 최소 차이이기 때문에

 

눈사람 높이 순으로 정렬한 뒤, 가장 근처에 있으면서 눈사람을 구성하는 눈덩이가 겹치지 않는 눈사람만 찾으면 되기 때문이다.

 

눈덩이가 겹치치 않는 눈사람을 찾은 뒤, 발견하면 바로 break 하는 방식으로 시간제한을 통과할 수 있었다.

 

위와 같은 아이디어를 바탕으로 구현하면 아래와 같다.

 

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

public class Main {
    int N;
    int [] arr;
    List<SnowMan> list = new ArrayList<>();
    int ans = Integer.MAX_VALUE;
    
    public static void main(String[] args) throws IOException {
        new Main().sol();
    }

    private void sol() throws IOException {
        setUp();
        getCombinations();
        Collections.sort(list, (a, b) -> a.height - b.height);
        getAns();
        System.out.println(ans);

    }

    private void getAns() {
        for (int i = 0; i < list.size()-1; i++) {
            for (int j = i+1; j < list.size(); j++) {
                SnowMan snowMan1 = list.get(i);
                SnowMan snowMan2 = list.get(j);
                if (snowMan1.idx1 != snowMan2.idx1 && snowMan1.idx1 != snowMan2.idx2 && snowMan1.idx2 != snowMan2.idx1 && snowMan1.idx2 != snowMan2.idx2) {
                    ans = Math.min(Math.abs(snowMan1.height - snowMan2.height), ans);
                    break;
                }
            }
        }
    }

    private void getCombinations() {
        for (int i = 0; i < N-1; i++) {
            for (int j = i+1; j < N; j++) {
                list.add(new SnowMan(i, j, arr[i] + arr[j]));
            }
        }
    }

    private void setUp() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        String[] input = br.readLine().split(" ");
        arr = new int[N];

        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(input[i]);
        }
    }

    static class SnowMan{
        int idx1;
        int idx2;
        int height;
        public SnowMan(int idx1, int idx2, int height) {
            this.idx1 = idx1;
            this.idx2 = idx2;
            this.height = height;
        }
    }
}

 

결과

 

 

2️⃣ 투 포인터 이용한 풀이

이분 탐색을 이용해서 문제를 해결할 수도 있다.

 

먼저, 이분탐색을 위해 눈덩이를 정렬해준다.

 

아이디어는 다음과 같다.

 

 

한 눈사람은 i번째 눈덩이와 j번째 눈덩이로 고정한다. (i와 j 사이에 최소 2개 이상의 눈덩이가 존재해야한다.)

 

그리고, 그 사이의 눈덩이들로 또 하나의 다른 눈사람을 구성한다.

 

눈사람을 구성할때마다 두 눈사람의 차이의 값을 구하고 값을 갱신해준다.

 

만약 투포인터로 구성한 눈사람의 크기가 고정된 눈사람보다 큰 경우 오른쪽 포인터를 감소하고

 

작은 경우 왼쪽 포인터를 증가하는 방식으로 진행시켜 두 눈 사람의 높이 차이가 최소가 될 수 있도록 한다.

 

다음은 위와 같이 j 를 이동시켜 고정된 눈사람을 다른 눈덩이로 조합해보고, 그 사이의 눈덩이들로 투 포인터를 수행하면 된다.

 

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

public class Main {
    int N;
    int[] arr;
    int ans = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        new Main().sol();
    }

    private void sol() throws IOException {
        setUp();
        Arrays.sort(arr);
        getAns();
        System.out.println(ans);
    }

    private void getAns() {
        for (int i = 0; i <= N - 4; i++) {
            for (int j = N - 1; j >= i + 3; j--) {
                int snowman1 = arr[i] + arr[j];
                int left = i + 1, right = j - 1;
                while (left < right) {
                    int snowman2 = arr[left] + arr[right];
                    if (snowman2 < snowman1) {
                        left++;
                    } else if (snowman2 > snowman1) {
                        right--;
                    } else {
                        System.out.println(0);
                        System.exit(0);
                    }
                    ans = Math.min(ans, Math.abs(snowman1 - snowman2));
                }
            }
        }
    }

    private void setUp() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        String[] input = br.readLine().split(" ");
        arr = new int[N];

        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(input[i]);
        }
    }

}

 

결과