개발자 Lim

<아이디어>

해당 문제의 핵심은 가변적으로 변하는 배열에서 높은 값을 가지는 것을 가져오는 걸 반복해야 한다는 점 이다.

처음에는 자동으로 값을 내림차순으로 정렬해주는 TreeSet<Integer>을 생각했으나 중복된 값이 제거 된다는 문제점이 있어 그 대안으로 조건식에 따라 값을 정렬해서 저장하는 PriorityQueue 우선순위 큐를 생각 할 수 있었다.

<우선 순위 큐>

https://velog.io/@gillog/Java-Priority-Queue%EC%9A%B0%EC%84%A0-%EC%88%9C%EC%9C%84-%ED%81%90

<정답 코드>

class Solution {
    // 시간 복잡도 O(n) 공간 복잡도 O(n)
    public int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> pQueue = new PriorityQueue<>(Collections.reverseOrder());
        for (int stone : stones)
            pQueue.add(stone);
        while(pQueue.size()>1){
            int stone1 = pQueue.remove();
            int stone2 = pQueue.remove();
            int newStone = Math.abs(stone1-stone2);
            if(newStone!=0)
                pQueue.add(newStone);
        }
        return pQueue.size()==0?0: pQueue.peek();
    }
}