BOJ_25945 : 컨테이너 재배치

👉 문제링크

---

---

🔸 문제 분석 🔸

• 총 m개의 컨테이너가 n개의 칸에 나누어 쌓여져 있다.
• n개의 각 칸의 컨테이너 높이가 1이하가 되도록 재배치할 때, 최소 이동 횟수를 출력한다.

🔸 문제 풀이 🔸

• 컨테이너의 높이를 평탄화 하는 문제이다.
• 가장 먼저 정렬을 n번 수행해서 최대값을  -1 최소값을 +1 하는 방법이 있다
  • n이 최대 10만이므로, 시간 복잡도는 O(n^2logn) 으로 1초를 초과하게 된다.
  • 최대힙, 최소힙 두 가지 우선순위 큐로 최대값과 최소값만 빠르게 구하는 방법이 있지만, 이 문제에서는 시간 초과가 나게 된다.
• 그리디 알고리즘으로 효율적으로 계산해야한다.
  • n개의 각 칸에 컨테이너는 결국 평균(m/n)에 수렴하게 된다.
  • 여기서 높이차가 1이하인 이유가 나오는데, 평균에 수렴할 때 몇 개의 칸은 평균+1의 값을 가진다.(m%n 개)
  • 여기서 정렬이 필요한데, 평균보다 작은 높이의 칸에서 평균+1 까지 늘리는 것이 아닌
    평균 보다 큰 높이의 칸에서 평균+1 까지 내려야 하는 것이다. 따라서 정렬이 필요하다.

🔸 코드 🔸

import java.io.*;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        Integer[] containers = new Integer[n];
        long sum = 0;

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

        Arrays.sort(containers, Collections.reverseOrder());

        int avg = (int) (sum / n);
        int remainder = (int) (sum % n);

        int[] target = new int[n];
        for (int i = 0; i < n; i++) {
            target[i] = avg + (i < remainder ? 1 : 0);
        }

        long moveCnt = 0;
        for (int i = 0; i < n; i++) {
            if (containers[i] > target[i]) {
                moveCnt += containers[i] - target[i];
            }
        }

        bw.write(Long.toString(moveCnt));
        bw.flush();
    }
}

🔸 코드 해석 🔸

• n개의 칸의 컨테이너 정보를 Integer 배열 containers에 저장하고, 총합을 long형 변수 sum에 누적한다.
• containers를 내림차순 정렬한다.
• 수렴할 평균 avg는 sum/n, 평균+1의 개수인 remainder는 sum%n으로 계산한다.
• containers 배열과 매칭 시킬 int배열 target에 remainder만큼 avg+1, 나머지는 agv 값을 넣는다.
• n개의 칸을 확인해서 target의 값이 더 큰 경우, 그 차이만큼 moveCnt에 누적한다.
  • target보다 작은 경우는 중복이므로 카운트하지 않는다.
• moveCnt를 출력한다.

---

🔸 end 🔸

• 처음에 2개의 우선순위 큐로 최대힙, 최소힙을 통해 최대값, 최소값을 빠르게 구하는 방식으로 풀이했는데 시간 초과가 났다.
• 시간 복잡도 상으로는 O(nlogn)으로 문제가 되지 않을 것 같았는데, 아마 그리디 풀이를 의도한 문제여서 시간 초과가 난 것 같다.
• 자주 등장할 것 같은 유용한 그리디 유형인 것 같아서 잘 기억해 둘 생각이다.