[LV.2][JAVA] 더 맵게

https://school.programmers.co.kr/learn/challenges?tab=algorithm_practice_kit

프로그래머스

푸는 동안 사고과정 및 개선점

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue<Integer> pq = new PriorityQueue();
        for(int i: scoville){
            pq.add(i);
        } // 기본이 min heap
        int s = 0;
        while(s<K){
            if(pq.isEmpty()){
                answer = -1;
                break;
            }
            int easy = pq.poll();
            int eeasy = pq.poll();
            s = easy + (2*eeasy);
            answer++;
        }
        
        
        return answer;
    }
}

처음에 문제이해를 완전히 잘못했다. 모든 음식의 스코빌지수가 K이상이 되어야한다.

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue<Integer> pq = new PriorityQueue();
        for(int i: scoville){
            pq.add(i);
        } // 기본이 min heap
        while(pq.peek()<K){
            if(pq.isEmpty()){
                answer = -1;
                break;
            }
            if(pq.size()>=2){
                int easy = pq.poll();
                int eeasy = pq.poll();
                pq.add(easy + (2*eeasy)); // 새 음식 만들어서 추가
                answer++;
            }
        }
        
        return answer;
    }
}

이게 수정한 코드다. 시간초과나는 엄청 큰 케이스를 제외하고서 다 통과된다...

조금만 생각해보면 해결되는 부분이었다. K 이상으로 음식을 만들면 되니까 minheap을 뽑았을 때 K이상인 경우 break를 줘버리는 것이다.

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue<Integer> pq = new PriorityQueue();
        for(int i: scoville){
            pq.add(i);
        } // 기본이 min heap
        while(pq.peek()<K){
            if(pq.size()>=2){
                int easy = pq.poll();
                int eeasy = pq.poll();
                pq.add(easy + (2*eeasy)); // 새 음식 만들어서 추가
                answer++;
            }else{
                answer = -1;
                break;
            }
            if(pq.peek() >= K) break;
        }
        
        return answer;
    }
}

pq 사이즈로 break 조건도 바꿔서 넣어봤다.

---

# 추가 공부

`PriorityQueue` 활용하기

기본이 minheap이다 그래서 reverseOrder해버리면 maxheap이 된다.

PriorityQueue<Integer> maxHeap = new PriorityQueue(Collections.reverseOrder());
PriorityQueue<Integer> maxHeap = new PriorityQueue((o1, o2)-> {return o2-o1;});

자료구조를 다른걸 사용할 때는 이렇게도 쓸 수 있다.

PriorityQueue<Student> pq = new PriorityQueue<>((s1, s2) -> {
    if (s1.grade == s2.grade) {
        return s1.name.compareTo(s2.name);
    }
    return s2.grade - s1.grade;
});

그리디한 문제를 풀 때 이렇게 하곤 했다.

 

도움이 됐다면 댓글이나 공감 버튼 한 번씩 누르고 가주세요!