[LeetCode] 1046. Last Stone Weight - Java

https://leetcode.com/problems/last-stone-weight/description/

Last Stone Weight - LeetCode

---

문제

You are given an array of integers stones where stones[i] is the weight of the ith stone.

We are playing a game with the stones. On each turn, we choose the heaviest two stones and smash them together. Suppose the heaviest two stones have weights x and y with x <= y. The result of this smash is:

• If x == y, both stones are destroyed, and
• If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x.

At the end of the game, there is at most one stone left.

Return the weight of the last remaining stone. If there are no stones left, return 0.

 

Example 1:

Input: stones = [2,7,4,1,8,1]
Output: 1
Explanation: 
We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then,
we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then,
we combine 2 and 1 to get 1 so the array converts to [1,1,1] then,
we combine 1 and 1 to get 0 so the array converts to [1] then that's the value of the last stone.

Example 2:

Input: stones = [1]
Output: 1

 

Constraints:

• 1 <= stones.length <= 30
• 1 <= stones[i] <= 1000

---

풀이

풀이 과정

1~30개 사이의 돌들의 무게가 담겨있는 배열 stones가 주어지고 주어진 돌들을 이용하여 게임을 진행한다.

주어진 돌들의 배열에서 가장 무거운 돌 두개를 선택하며 다음 과정을 반복한다.

• 두 개의 돌을 각각 x, y라고 할 때 x <= y 이다.
• x와 y의 무게 같은 경우 두 개의 돌을 모두 파괴한다.
• 만약 x와 y의 무게가 같지 않은 경우 x를 파괴하고 y - x무게 만큼의 새로운 돌의 무게를 배열에 다시 추가한다.
• 마지막 남은 돌의 무게를 return 한다, 남은 돌이 없는 경우에는 0을 return한다.

 

우선 배열의 길이가 1인 경우에는 해당 돌의 무게값을 바로 return한다.

// 돌의 개수가 한 개인 경우 해당 돌의 무게를 바로 return
if(stones.length == 1) return stones[0];

 

무게별로 순차적으로 탐색하고 새로운 돌의 무게가 추가되는 경우가 있으므로 우선순위 큐를 이용한다.
가장 무거운 돌을 비교하므로 높은 값이 우선순위를 갖도록 큐를 선언해준다.

// 돌의 무게를 무거운 순으로 저장할 우선순위 큐
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

 

배열에 있는 모든 값을 큐에 삽입한다.

// 모든 돌을 우선순위 큐에 삽입
for(int i : stones) pq.offer(i);

 

큐에 남은 값이 1개 이하가 될 때까지 탐색을 반복한다.

조건에 맞도록 우선순위가 높은 두 개의 값을 각각 x, y로 큐에서 추출하고 두 값이 같지 않은 경우 y - x의 값을 다시 우선순위 큐에 삽입한다.

// 우선순위큐에 남은 돌의 개수가 한 개 이하가 될 때까지 반복
while(pq.size() > 1){
    // 가장 무거운 돌 두 개 꺼냄
    int y = pq.poll();
    int x = pq.poll();

    // x와 y의 무게가 같지 않은 경우 y-x의 무게를 다시 우선순위 큐에 삽입
    if(x != y) pq.offer(y - x);
}

 

큐에 남아있는 값이 있는 경우 해당 값을 return 하고 남아있는 값이 없는 경우에는 0을 return 한다.

// 우선순위큐에 남은 값이 있는 경우 해당 값을 return
// 남은 값이 없는 경우 0을 return
return pq.size() == 0 ? 0 : pq.poll();

---

최종 코드

class Solution {
    public int lastStoneWeight(int[] stones) {
        // 돌의 개수가 한 개인 경우 해당 돌의 무게를 바로 return
        if(stones.length == 1) return stones[0];

        // 돌의 무게를 무거운 순으로 저장할 우선순위 큐
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

        // 모든 돌을 우선순위 큐에 삽입
        for(int i : stones) pq.offer(i);

        // 우선순위큐에 남은 돌의 개수가 한 개 이하가 될 때까지 반복
        while(pq.size() > 1){
            // 가장 무거운 돌 두 개 꺼냄
            int y = pq.poll();
            int x = pq.poll();

            // x와 y의 무게가 같지 않은 경우 y-x의 무게를 다시 우선순위 큐에 삽입
            if(x != y) pq.offer(y - x);
        }

        // 우선순위큐에 남은 값이 있는 경우 해당 값을 return
        // 남은 값이 없는 경우 0을 return
        return pq.size() == 0 ? 0 : pq.poll();
    }
}

---