[백준 Java] 20366번 같이 눈사람 만들래?

💡문제

[Gold III] 같이 눈사람 만들래? - 20366

문제 링크

성능 요약

메모리: 24644 KB, 시간: 380 ms

---

🤔접근법

주어진 정수의 배열에서 두 정수의 쌍을 두개 만든 후 두 쌍 간의 합의 차이가 최소가 될때 그 최소값을 출

범위 체크 및 시간복잡도 예상

• 4 ≤ N ≤ 600
• 1 ≤ Hi ≤ $10^9$
• $O(N^4)$은 시간초과

풀이법

❌ 접근 방법. 완탐

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

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

⭕ 접근 방법. 완탐

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

➡️ 해당 풀이법의 시간 복잡도 : $O(N^2)$

⭕ 접근 방법. 투포인터

1. 눈덩이 크기 정렬 → $O(N^2)$
2. 엘사가 만든 몸통, 머리 눈덩이 선택 → $O(N^2)$
3. 엘사가 선택하지 않은 눈덩이들을 이용해서 엘사 눈사람의 키와 가장 가까운 값을 가지는 두 눈덩이 선택 → : $O(N)$

➡️ 해당 풀이법의 시간 복잡도 : $O(N^3)$

---

🤯FAIL

답을 봐서 문제를 푼 경우

• 해결이 되지 않은 부분 : 눈사람을 만든 후에 비교하지 않고 눈덩이들의 차이를 비교해두고 그 눈덩이들의 차이가 작은 두개를 찾아서 눈사람을 만들려고 했다. 근데 이때 눈덩이의 차이가 작은 걸로 눈사람 하나를 이미 만들어버린 경우 최소가 되지 않는 경우가 발생했고 이를 해결하지 못해서 답을 봤다.
• 정답의 로직은 ?
  눈사람으로 만들 수 있는 조합을 모두 만든 후에 그 눈사람의 키의 차이가 작은 눈사람을 두개를 선택하였고 마지막에 네개의 눈덩이가 중복되지 않는지 확인하였다.
  추가로 투포인터 풀이도 생각나지 않아서 정답을 봤는데 지난번 스터디때 N^x 인 경우 N^x-1 *logN으로 만들 수 있는 문제들이 있다고 했는데 이 문제가 그런 경우 인거 같다.

👩‍💻 코드

🅰️ 완탐

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main_20366 {
    static int N;  // 배열의 요소 수
    static int snow[];  // 눈의 높이를 저장하는 배열
    static ArrayList<Snowman> snowmans;  // Snowman 객체를 저장하는 ArrayList

    static class Snowman implements Comparable<Snowman> {
        int headSnowIdx;
        int bodySnowIdx;
        int height;

        // Snowman 클래스의 생성자
        public Snowman(int head, int body, int height) {
            this.headSnowIdx = head;
            this.bodySnowIdx = body;
            this.height = height;
        }

        // 높이를 기준으로 Snowman 객체를 정렬하기 위한 compareTo 메서드 재정의
        @Override
        public int compareTo(Snowman o) {
            return this.height - o.height;
        }
    }

    static int min = Integer.MAX_VALUE;  // 최소 높이 차이를 저장하는 변수

    public static void main(String[] args) throws IOException {
        // BufferedReader를 사용한 입력 처리
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        // 눈의 높이를 저장하는 배열 초기화
        snow = new int[N];

        // 눈의 높이를 읽고 배열 'snow'를 채움
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            snow[i] = Integer.parseInt(st.nextToken());
        }

        // Snowman 객체를 저장하는 ArrayList 초기화
        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]));
            }
        }

        // Snowman 객체를 높이를 기준으로 정렬
        Collections.sort(snowmans);

        // 연속적인 Snowman 객체 간의 높이 차이를 저장하는 ArrayList 초기화
        for (int i = 0; i < snowmans.size() - 1; i++) {
            Snowman snowman = snowmans.get(i);
            Snowman nextSnowman = snowmans.get(i + 1);
            int snow1 = snowman.bodySnowIdx;
            int snow2 = snowman.headSnowIdx;
            int snow3 = nextSnowman.bodySnowIdx;
            int snow4 = nextSnowman.headSnowIdx;

            // 두 Snowman 객체가 겹치지 않을 때 높이 차이를 계산하여 최소값 갱신
            if (snow1 != snow3 && snow1 != snow4 && snow2 != snow3 && snow2 != snow4) {
                min = Math.min(min, nextSnowman.height - snowman.height);
            }
        }

        // 최소 높이 차이를 출력
        System.out.println(min);
    }
}

🅱️ 투포인터

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

public class Main_20366 {
    static int N;  // 눈의 개수
    static int snow[];  // 눈의 높이를 저장하는 배열
    static int min = Integer.MAX_VALUE;  // 최소 높이 차이를 저장하는 변수

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        snow = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            snow[i] = Integer.parseInt(st.nextToken());
        }

        // 눈의 높이 배열을 정렬
        Arrays.sort(snow);

        // 두 개의 Snowman을 생성하고 그 높이 차이를 계산하는 중첩된 반복문
        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                int snowMan1 = snow[i] + snow[j];
                int start = 0;
                int end = N - 1;

                // 투 포인터를 사용하여 두 개의 Snowman 높이를 비교하고 최소 높이 차이를 찾는 루프
                while (start < end) {
                    // 현재 포인터가 이미 사용된 눈의 인덱스와 일치하는 경우 다음 눈으로 이동
                    if (start == i || start == j) {
                        start++;
                        continue;
                    }
                    if (end == i || end == j) {
                        end--;
                        continue;
                    }

                    int snowMan2 = snow[start] + snow[end];
                    min = Math.min(min, Math.abs(snowMan1 - snowMan2));

                    // 높이 차이에 따라 포인터 이동
                    if (snowMan1 > snowMan2)
                        start++;
                    else if (snowMan1 < snowMan2)
                        end--;
                    else {
                        // 높이 차이가 0이면 더 이상의 계산이 필요 없으므로 0을 출력하고 종료
                        System.out.println(0);
                        return;
                    }
                }
            }
        }

        // 최소 높이 차이 출력
        System.out.println(min);
    }
}