[코딩테스트] 백준 19638번 센티와 마법의 뽕망치 - JAVA

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

 

Problem 💻

문제

센티는 마법 도구들을 지니고 여행을 떠나는 것이 취미인 악당이다.

 

거인의 나라에 도착한 센티는 자신보다 키가 크거나 같은 거인들이 있다는 사실이 마음에 들지 않았다.

 

센티가 꺼내 들은 마법 도구는 바로 마법의 뿅망치로, 이 뿅망치에 맞은 사람의 키가 ⌊ 뿅망치에 맞은 사람의 키 / 2 ⌋로 변하는 마법 도구이다. 단, 키가 1인 경우 더 줄어들 수가 없어 뿅망치의 영향을 받지 않는다.

 

하지만 마법의 뿅망치는 횟수 제한이 있다. 그래서 센티는 마법의 뿅망치를 효율적으로 사용하기 위한 전략을 수립했다. 바로 매번 가장 키가 큰 거인 가운데 하나를 때리는 것이다.

 

과연 센티가 수립한 전략에 맞게 마법의 뿅망치를 이용한다면 거인의 나라의 모든 거인이 센티보다 키가 작도록 할 수 있을까?

입력

첫 번째 줄에는 센티를 제외한 거인의 나라의 인구수 N (1 ≤ N ≤ 105)과 센티의 키를 나타내는 정수 Hcenti (1 ≤ Hcenti ≤ 2 × 109), 마법의 뿅망치의 횟수 제한 T (1 ≤ T ≤ 105)가 빈칸을 사이에 두고 주어진다.

 

두 번째 줄부터 N개의 줄에 각 거인의 키를 나타내는 정수 H (1 ≤ H ≤ 2 × 109)가 주어진다.

출력

마법의 뿅망치를 센티의 전략대로 이용하여 거인의 나라의 모든 거인이 센티보다 키가 작도록 할 수 있는 경우, 첫 번째 줄에 YES를 출력하고, 두 번째 줄에 마법의 뿅망치를 최소로 사용한 횟수를 출력한다.

 

마법의 뿅망치를 센티의 전략대로 남은 횟수 전부 이용하고도 거인의 나라에서 센티보다 키가 크거나 같은 거인이 있는 경우, 첫 번째 줄에 NO를 출력하고, 두 번째 줄에 마법의 뿅망치 사용 이후 거인의 나라에서 키가 가장 큰 거인의 키를 출력한다.

 

Solution 💡

센티는 자신보다 큰 거인들을 마법의 뿅 망치로 때리는 문제이다. 뿅 망치로 맞은 사람의 키는 반으로 줄고, 키가 1인 경우 더 이상 망치로 때리지 못한다.

 

때릴 수 있는 망치에 횟수가 정해져 있기 때문에 가장 효율적인 방법으로 진행하여야 한다.

 

여기서 말하는 가장 효율적인 방법은 가장 큰 거인부터 때리면서 진행하는 것이다. 가장 큰 거인부터 정렬하기 위해 우선순위 큐를 사용하였고 내림차순을 할 수 있게 Collections.reverseOrder()을 선언해 주었다.

 

두 개의 루프가 존재하며, 거인의 키 입력값을 넣는 루프와 때릴 수 있는 뽕망치 횟수 만큼 돌아가는 루프가 있다.

 

뽕망치 횟수 루프 안에 조건문을 넣어 센티보다 더 이상 큰 거인이 없는 경우와 가장 큰 거인의 키가 1이 되면 뽕망치를 때리면 안되는 두 조건을 넣어 탈출코드를 만들었다.

 

위 조건에 만족하지 않는다는 것은 뽕망치를 사용한다는 것이므로 큐에서 poll()을 진행하여 반으로 나누고 다시 큐에 add 해준다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int N,H,T;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

				// N: 거인나라 인구수, H:센티의 키, T: 뽕망치 횟수 제한
        N = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());
        T = Integer.parseInt(st.nextToken());

        String answer = "NO";
        Queue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

				// 큐에 데이터를 삽입하여 내림차순 정렬한다.
        for (int i = 0; i < N; i++) {
            pq.add(Integer.parseInt(br.readLine()));
        }
        
        
        int cnt = 0;
        for (int i = 0; i < T; i++) {
            // 최장신이 나보다 작거나 1일경우 break;
            if ((pq.peek() < H) || (pq.peek() == 1)) break;
            cnt++;
            pq.add(pq.poll() / 2);
        }
        
        // 루프가 끝난 뒤 거인의 최장신과 센티의 키를 비교하여 출력조건을 만든다.
        if (pq.peek() < H) answer = "YES";
        StringBuilder sb = new StringBuilder(answer);
        sb.append("\n").append(answer.equals("YES") ? cnt : pq.poll());
        System.out.print(sb);
    }
}