자바 (백준) 19638 센티와 마법의 뿅망치

오답 노트 & 새로 알게 된 점

이번 문제는 우선순위 큐 문제이다.

 

N <= 10^5인데, 이 때 키 순으로 항상 정렬하면 N^2logN일 것 같아서 TLE가 난다.

그래서 정렬이 logN인 힙을 사용하여 최대힙을 만들어 문제를 풀게 된다.

 

항상 자료구조에 관한 문제(스택, 큐)를 풀게 되면 항상 NPE가 신경 쓰인다.

 

이번에도 pro 메서드에서 for문이 끝나고 마지막 if-else문에서 

단지 if문만 계속 써서 틀렸다고 나왔다. 

 

내 생각에는 YES할 경우에는 무조건 for문에서 sb에 포함시켜 return 된다고 생각했다.

 

그러나 마지막 망치질에 의해 YES가 나올 수 있다고 생각이 들어 if-else로 사용하여 문제를 풀었다.

 

이 문제에서 깨달은 점은 처음에 문제를 접근할 때, 망치의 limit수가 나왔다.

나는 이것을 보자마자 cnt라는 변수를 생각하여 망치를 사용할 때마다 cnt를 더해주었고, 

반복문을 나오는 조건을 cnt < limit로 했다.

 

물론 위의 방법처럼 풀어도 되지만 아래의 풀이처럼 생각하는 방법도 길러야겠다.

 

---

코드

package Data_Structure;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class BOJ19638 {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static int N;
    static int std; //기준 키
    static int limit; //망치 제한
    static PriorityQueue<Integer> pq = new PriorityQueue<>((o1,o2)->{
        return o2.compareTo(o1);
    });
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = atoi(st.nextToken());
        std = atoi(st.nextToken());
        limit = atoi(st.nextToken());
 
        for (int i = 0; i < N; i++) {
            pq.offer(atoi(br.readLine()));
        }
 
        pro();
 
        System.out.println(sb);
    }
 
    static void pro() {
        for (int i = 0; i < limit; i++) {
 
            int num = pq.peek();
 
            if(num < std) {
                sb.append("YES" + "\n" + i);
                return;
            }
 
            else if(num > 1){
                pq.poll();
                pq.offer(num / 2);
            }
        }
//
//        for (Integer integer : pq) {
//            System.out.println(integer);
//        }
        if(pq.peek() >= std) sb.append("NO").append("\n").append(pq.peek());
        else sb.append("YES").append("\n").append(limit);
    }
}