항해 99클럽 코딩테스트 스터디 21일차 TIL (자바 / 비기너)

<오늘의 학습 키워드>

- 우선순위 큐

<오늘의 문제>

제목 : 백준 / 실버1 / 19638번 센티와 마법의 뿅망치

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

<풀이>

정답은 더보기

package BOJ.DP.센티와마법의뿅망치.insub2004_241117;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Collection;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(stringTokenizer.nextToken());
        int centiHeight = Integer.parseInt(stringTokenizer.nextToken());
        int hammerMinCount = Integer.parseInt(stringTokenizer.nextToken());

        PriorityQueue<Integer> giantDescendingQueue = new PriorityQueue<>(Collections.reverseOrder());

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

        int answer = 0;
        for (int i = 0; i < hammerMinCount; i++) {
            if (giantDescendingQueue.peek() < centiHeight || giantDescendingQueue.peek() == 1) {
                break;
            }
            int tallGiant = giantDescendingQueue.poll();
            giantDescendingQueue.add(tallGiant/2);
            answer++;
        }

        if (giantDescendingQueue.peek() >= centiHeight) {
            System.out.println("NO");
            System.out.println(giantDescendingQueue.poll());
        } else {
            System.out.println("YES");
            System.out.println(answer);
        }
    }
}

 

• 첫 입력으로 거인의 수, 센티의 키, 뿅망치 최소 횟수를 받아서 각 변수에 저장
• 우선순위 큐를 제일 키가 큰 거인이 head에 위치하도록 내림차순 정렬로 생성, 거인들(거인의키)을 우선순위 큐에 저장
• 저장이 끝난 큐를 뿅망치 최소 횟수만큼 반복하면서 제일 앞에있는 거인의 키 확인
  • 제일 앞에 있는 거인이 큐안에서 제일 키가 크기 때문에 제일 앞에있는 거인만 체크해줘도 된다.
  • 제일 앞에있는 거인의 키가 센티보다 작거나, 키가 1이면 뿅망치 횟수가 남아있어도 최소 사용횟수를 결과로 출력해야하기 때문에 break;로 반복문을 빠져나온다.
  • 위의 조건에 걸리지 않으면 제일 큰 거인을 poll로 꺼내서 나누기 2 하고 다시 큐에 넣는다.
• 반복문을 빠져나오면 다시 한번 큐의 맨 앞에 있는 거인의 키를 기준으로 정답을 출력한다.

<결론, 주의할점>