[Programmers 문제풀이 JAVA] Level 2 더 맵게

 

📄 더 맵게

🔗 문제 풀러가기

---

문제의 접근은 Min-Heap을 이용해 해결할 수 있습니다. 문제의 조건을 보면 주어진 원소들 중 가장 작은 값 과 두 번째로 작은 값 을 연산하여 새로운 값을 생성 합니다. 여기서 새로운 값이 항상 작다는 보장이 없습니다. 따라서 새로운 값을 생성한 뒤 다시 오름차순으로 정렬을 해야합니다. Min-Heap을 이용하면 가장 작은 작은 값이 항상 맨 앞에 있으므로 문제를 푸는데 쉽게 접근할 수 있습니다. 문제의 풀이 순서는 다음과 같습니다.

Java에서 문제의 풀이는 PriorityQueue를 사용하였습니다.

1. 주어진 모든 원소(scoville)를 우선선위 큐에 넣는다
2. 첫 번째 원소의 값이 K값 이상인지 확인한다.
3. K값 이하일 경우 첫 번째 원소와 두 번째 원소를 꺼내 새로운 값을 만든다.
4. 새로운 값을 우선순위 큐에 넣는다.
5. 우선순위 큐의 총 원소 개수가 2개 이상인지 확인한다. (2번부터 반복한다.)

글보단 소스코드를 보면 쉽게 이해할 수 있습니다.

 

---

🌱 Solution 함수

public int solution(int[] scoville, int K) {
    int answer = 0;
    PriorityQueue<Integer> scovilleQueue = new PriorityQueue<>();

    for (int item : scoville)
    scovilleQueue.add(item);

    while(scovilleQueue.size() > 1 && scovilleQueue.peek() < K){
        int firstScoville = scovilleQueue.poll();
        int secondScoville = scovilleQueue.poll();
        scovilleQueue.add(firstScoville + (secondScoville * 2));
        answer++;
    }

    return scovilleQueue.peek() < K ? -1 : answer;
}

---

🔈 궁금한점이 있다면?

댓글 또는 Github Issues 남겨주세요. 모르는 부분이 있다면 함께 고민해서 문제를 해결해보아요

💡 Github에 더 많은 문제 풀이가 있습니다.

Programmers 문제 풀이

BaekJoon Online Judge 문제 풀이