[백준 골드3] 20366번: 같이 눈사람 만들래? - Java

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

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

 

문제
언니! 똑...똑똑...똑똑! 같이 눈사람 만들래~? ♪
언니 엘자와 동생 안나에게는 N개의 눈덩이가 있다. 각 눈덩이 i (1 ≤ i ≤ N)의 지름은 Hi 이다. 하나의 눈사람은 두 개의 눈덩이로 구성되며, 눈덩이 하나를 아래에 두고 그 눈덩이보다 크지 않은 다른 눈덩이를 쌓아올리는 방식으로 만들 수 있다. 이때, 눈사람의 키는 두 눈덩이 지름의 합과 같다.
엘자와 안나는 눈덩이 N개 중 서로 다른 4개를 골라서 눈사람을 각각 1개씩, 총 2개를 만들려고 한다. 두 자매는 두 눈사람의 키의 차이가 작을수록 두 눈사람의 사이가 좋을 것이라고 믿는다. 우리는 엘자와 안나가 가장 사이좋은 두 눈사람을 만들기 위해서 도와주려고 한다.
주어진 N개의 눈덩이를 이용하여 만들 수 있는 두 눈사람의 키 차이 중 최솟값을 구하는 프로그램을 작성하시오.

입력
첫째 줄에 N (4 ≤ N ≤ 600)이 주어진다.
둘째 줄에는 각 눈덩이 i (1 ≤ i ≤ N)의 지름을 의미하는 정수 Hi (1 ≤ Hi ≤ 109)가 공백으로 구분되어 주어진다.

출력
만들 수 있는 두 눈사람의 키 차이 중 최솟값을 나타내는 정수를 출력하라.

예제 입력 1 
5
3 5 2 5 9
예제 출력 1 
1
높이가 (2, 5), (3, 5)로 구성된 눈사람 둘을 만드는 것이 최적의 경우 중 하나이다. |7-8| = 1
다른 경우로는 (2, 9), (5, 5)로 두 눈사람을 만드는 경우가 있다. |11-10| = 1

---

알고리즘: 정렬, 투포인터

풀이

값 저장을 위해 Snowman 정적 멤버 클래스를 만들어 사용했다. (int[]을 사용해도 된다)

모든 가능한 눈사람 키 합을 계산해 List<Snowman> list에 넣은 뒤, 인접 값끼리 차이를 비교해 차이가 적은 경우를 찾았다.

list를 정렬하기 위해 Compartor를 int인 sum 필드를 비교하도록 커스텀했다.

=> Collections.sort(list, Comparator.comparingInt(snowman->snowman.sum));

두 눈사람의 모든 i, j가 달라야 함에 유의해야 했다. (i, j는 단순히 두 눈덩이)

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

public class Main
{
    static class Snowman {
        int sum, i, j;
        Snowman(int sum, int i, int j) {
            this.sum = sum;
            this.i = i;
            this.j = j;
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] s = br.readLine().split(" ");
        int[] arr = new int[n];
        for(int i=0; i<n; i++) {
            arr[i] = Integer.parseInt(s[i]);
        }
        // 모든 만들어질 수 있는 스노우맨을 저장
        List<Snowman> list = new ArrayList<>();
        for(int i=0; i<n; i++) {
            for(int j=i+1; j<n; j++) {
                list.add(new Snowman(arr[i]+arr[j], i, j));
            }
        }
        Collections.sort(list, Comparator.comparingInt(snowman->snowman.sum));
        
        int min = Integer.MAX_VALUE;
        for(int i=0; i<list.size()-1; i++) {
            Snowman a = list.get(i);
            Snowman b = list.get(i+1);
            if (a.i != b.i && a.i != b.j && a.j != b.i && a.j != b.j)
                min = Math.min(min, Math.abs(list.get(i).sum - list.get(i+1).sum));
        }
        System.out.println(min);
    }
}