더 맵게

작성일: 2024-10-28

문제 링크 : [https://school.programmers.co.kr/learn/courses/30/lessons/42626]

접근 방식

• 우선순위큐를 이용해서, 자동 정렬되도록 함.
• while문을 돌려서, que에서 가장 작은 수가 (맨 앞), K이상이 되도록 함.
• while문이 한 번 돌 때마다, answer+1

잘못된 접근

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue <Long> que = new PriorityQueue<>();
        for(int s:scoville) que.offer((long)s);

        while(que.peek()<K){
            long one = que.poll();
            long two = que.poll() * 2;
            que.offer(one+two);
            answer++;
        }

        return answer;
    }
}

채점에서 일부 상황에, 런타임 에러가 발생하였다.

코드를 살펴보다 이상한 점을, 발견했다. 무한정으로 코드를 반복시키면, 무조건 음식은 K이상의 스코빌을 갖게 된다.

하지만, 예외가 있다. 바로 음식의 개수가 부족한 경우이다.

현재, 런타임 에러가 발생하는 이유는 que 사이즈가 부족한데, poll()을 통해 값을 가져오려고 해서, null 연산이 발생해서 런타임 에러가 발생한 것이다.

잘못 된 접근2

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue <Long> que = new PriorityQueue<>();
        for(int s:scoville) que.offer((long)s);

        while(que.peek()<K){
            long one = que.poll();
            long two = que.poll() * 2;
            que.offer(one+two);
            answer++;
            if(que.size()==1) return -1;
        }

        return answer;
    }
}

큐 사이즈가 1인 경우, 리턴하도록 했다.

이제는 런타임 에러는 발생하지 않지만, 일부 테스트케이스에서 실패가 나왔다.

if문의 위치가 잘못되었다. 꺼내기 전에 que의 사이즈를 확인했어야 했기 때문이다.

결과

소스 코드

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue <Long> que = new PriorityQueue<>();
        for(int s:scoville) que.offer((long)s);
        while(que.peek()<K){
            if(que.size()==1) return -1;
            long one = que.poll();
            long two = que.poll() * 2;
            que.offer(one+two);
            answer++;
        }
        return answer;
    }
}

다른 접근 방식

없음.

알게 된 점

없음.

[https://school.programmers.co.kr/learn/courses/30/lessons/42626]: