[NeetCode-LeetCode] Last Stone Weight JAVA

반응형

728x90

[NeetCode-LeetCode] Last Stone Weight - Easy 

---

접근

• 힙

---

풀이

배열에 돌의 무게가 주어지고 두 개의 돌을 부딪혀 새로운 무게의 돌을 만들어 낼 때 마지막에 남는 돌의 무게를 반환하는 문제이다. 두 돌의 무게가 같다면 모두 부서져 사라지고 무게가 다를 경우 무거운 돌의 무게에서 가벼운 돌의 무게를 뺀 만큼의 무게를 가진 돌이 새로 생기게 된다. 돌은 무거운 순서대로 부딪히게 되어 우선순위 큐를 사용해 주면 간단하게 해결할 수 있는 문제이다.

    public int lastStoneWeight(int[] stones) {
         PriorityQueue<Integer> pq = new PriorityQueue<>((a,b) -> b - a);

        for (int stone : stones) {
            pq.offer(stone);
        }

        while (pq.size() > 1) {
            int stone1 = pq.poll();
            int stone2 = pq.poll();

            int newStone = stone1 - stone2;

            if(newStone != 0){
                pq.offer(newStone);
            }
        }

        if(pq.isEmpty()) return 0;

        return pq.poll();
    }

우선순위 큐를 내림차순으로 정렬해주고 두 개의 돌이 무게가 다른 경우에만 새로운 무게를 가진 돌을 생성해 다시 큐에 넣어주었다. 큐에 존재하는 원소가 1개 이하가 될 경우 종료되고 큐가 비어있다면 마지막 남았던 두 개의 돌이 무게가 같아 부서져 없어져버린 경우로 0을 반환하고 그렇지 않은 경우 남아있는 돌의 무게를 반환한다. 

---

전체 코드

class Solution {
    public int lastStoneWeight(int[] stones) {
         PriorityQueue<Integer> pq = new PriorityQueue<>((a,b) -> b - a);

        for (int stone : stones) {
            pq.offer(stone);
        }

        while (pq.size() > 1) {
            int stone1 = pq.poll();
            int stone2 = pq.poll();

            int newStone = stone1 - stone2;

            if(newStone != 0){
                pq.offer(newStone);
            }
        }

        if(pq.isEmpty()) return 0;

        return pq.poll();
    }
}