Leetcode[day12] - Last Stone Weight

We have a collection of stones, each stone has a positive integer weight.
Each turn, we choose the two heaviest stones and smash them together. 
Suppose the stones have weights x and y with x <= y.  The result of this smash is:
If x == y, both stones are totally destroyed;
If x != y, the stone of weight x is totally destroyed, and the stone of weight y has new weight y-x.
At the end, there is at most 1 stone left.  Return the weight of this stone (or 0 if there are no stones left.)

Input: [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 last stone.

1. 알고리즘을 해결하기 위해서 생각한 방법

 

 - 어떤 자료구조를 사용해서 풀까, 고민을 했음.

 - 무게가 무거운 돌 2개를 꺼내서 사용한다고 생각을 했고, Stack을 사용하면 편할 것이라고 생각을 함.

 - 처음에 갖고 있는 stones를 stack 부어줌.

 - stack의 사이즈가 1이면, 루프를 종료함.

 - 그 외의 케이스에서는 stack을 sort를 하고, Math.abs를 통해서, 새로운 돌을 만들어줌.

 - 이것을 반복함.

 

2. 알고리즘 작성 중, 어려운 점

 

 - 큰 생각없이 풀기에는 무난했음

 - ㅋㅋㅋㅋ결과는 멀고 멀었음

 

3. 내가 작성한 알고리즘

 

class Solution {
    public int lastStoneWeight(int[] stones) {
        Stack<Integer> stack = new Stack();
        for(int i=0; i<stones.length; i++){
            stack.add(stones[i]);    
        }
        
        while(true){
            if(stack.size() <= 1){
                break;
            }
            Collections.sort(stack, (a,b)->a-b);
            int stoneWeight1 = stack.pop();
            int stoneWeight2 = stack.pop();
            System.out.println("StoneWeight1:"+stoneWeight1+" StoneWeight2:"+stoneWeight2);
            if(stoneWeight1 != stoneWeight2){
                int newStone = Math.abs(stoneWeight1 - stoneWeight2);
                stack.add(newStone);
            }
        }
        int result = 0;
        if(stack.size() != 0){
            result = stack.pop();
        }
        return result;
    }
}

4. 내가 작성한 알고리즘 결과

 

풀긴 풀었네...

5. 내가 작성한 알고리즘 리팩토링 해보기

 

 - Collections.sort()를 항상 하는 로직,

 루프문 안에서 Collections.sort()를 하는게 찝찝했고, 리팩토링 하게되면, 해당 로직을 개선해야 겠다고 생각을 했음.

 

 - queue보다 더 효율적인 자료구조가 있지 않을까?

 무게별로 계속해서 들어가야하니까, 트리 구조인 PriorityQueue를 reverseOrder()를 시켜서, 관리하면 좋겠다고 생각함.

 

6. 내가 작성한 리팩토링 알고리즘

 

 - Stack을 PriorityQueue로 변경

class Solution {
    public int lastStoneWeight(int[] stones) {
        Queue<Integer> queue = new PriorityQueue<>(Comparator.reverseOrder());
        for(int i=0; i<stones.length; i++){
            queue.offer(stones[i]);    
        }
        
        while(true){
            if(queue.size() <= 1){
                break;
            }
            int stoneWeight1 = queue.poll();
            int stoneWeight2 = queue.poll();
            System.out.println("StoneWeight1:"+stoneWeight1+" StoneWeight2:"+stoneWeight2);
            if(stoneWeight1 != stoneWeight2){
                int newStone = Math.abs(stoneWeight1 - stoneWeight2);
                queue.offer(newStone);
            }
        }
        int result = 0;
        if(queue.size() != 0){
            result = queue.poll();
        }
        return result;
    }
}

 

7. 결과

오잉?? 복붙이 아니라, 결과는 그대로임.

 8. 해당 결과를 통해 생각한 점

 

 음, 자료구조를 변경하는게 답이 아니라는 것을 알았음.

 그래서, PriorityQueue의 insert 시간 복잡도를 찾아보니 O(logN)이라는 것을 알았음. 

 

9. 다른 사람이 작성한 알고리즘을 보고 배운점

 

 다른 사람이 작성한 알고리즘을 찾아 봤는데, 희안하게 내 알고리즘이랑 똑같았음.

 어디서 시간을 잡아 먹을까, 고민 또 고민을 했는데, 정답은 System.out.print를 하는 것 때문에 느렸음.

 이번에는 잘 했음.

 

문제 : https://leetcode.com/explore/challenge/card/30-day-leetcoding-challenge/529/week-2/3297/

Explore - LeetCode