[99클럽 21일차] [백준] 19638 센티와 마법의 뿅망치

문제 분석

센티는 거인의 나라에서 자신보다 키가 큰 거인들을 마법의 뿅망치로 처리하려 한다. 뿅망치 사용 규칙은 아래와 같다.

1. 매번 가장 키가 큰 거인을 찾아 뿅망치로 키를 절반으로 줄인다.
2. 모든 거인의 키가 센티보다 작아질 때까지 최소 횟수로 뿅망치를 사용.
3. 제한된 횟수로 목표를 달성하지 못하면 남은 거인 중 가장 키가 큰 값을 출력.

문제 해결 접근

초기 접근 : 배열과 정렬

처음에는 배열을 사용해 거인의 키를 관리하고, 매번 정렬하여 최댓값을 찾아 처리하는 방식으로 접근했었다. 하지만 역시나 시간초과가 걸려있었기에 이 방식은 사용이 불가능했다. 매번 배열 정렬이 필요하므로 O(N log N)의 시간이 소요된다.

개선된 접근 : 우선순위 큐

우선순위 큐는 최댓값/ 최솟값을 효율적으로 가져올 수 있는 자료구조이다.

• 최댓값 관리 : O(log N) 시간으로 가장 큰 값을 가져오고 갱신 가능.
• 빠른 삽입과 삭제 : 키를 절반으로 줄인 값을 다시 삽입하는 연산도 효율적.

코드 구현

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        int Hcenti = Integer.parseInt(input[1]);
        int T = Integer.parseInt(input[2]);

        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);

        for (int i = 0; i < N; i++) {
            pq.add(Integer.parseInt(br.readLine()));
        }

        int hammerUsed = 0;

        while (!pq.isEmpty() && hammerUsed < T) {
            int tallest = pq.poll();

            if (tallest < Hcenti) break;

            if (tallest == 1) {
                pq.add(tallest);
                break;
            }

            pq.add(tallest / 2);
            hammerUsed++;
        }

        int tallestAfter = pq.isEmpty() ? 0 : pq.peek();

        if (tallestAfter < Hcenti) {
            System.out.println("YES");
            System.out.println(hammerUsed);
        } else {
            System.out.println("NO");
            System.out.println(tallestAfter);
        }
    }
}