[LeetCode/Easy] 1046. Last Stone Weight

1. Input

1) int[] stones

 

2. Output

1) 돌이 1개가 남을 때까지 다음과 같은 과정을 거쳤을 때 남은 돌의 무게를 반환

- 돌들 중 가장 무거운 2개를 골라서 돌들끼리 부딪히게 한다.

- 두 돌의 무게가 같다면 둘 다 파괴되어 없어진다.

- 두 돌의 무게가 다르다면 둘 중 가벼운 것은 파괴되고 더 무거운 돌은 가벼운 돌만큼 무게가 줄어든다.

2) 돌이 남지 않았다면 0을 반환

 

3. Constraint

1) 1 <= stones.length <= 30

2) 1 <= stones[i] <= 1000

 

4. Example

Input: stones = [2,7,4,1,8,1] -> Output: 1

설명:

- 7과 8을 고른다. -> 7은 파괴되고 8은 1이 된다. -> stones = [2,4,1,1,1]

- 2와 4를 고른다. -> 2는 파괴되고 4는 2가 된다. -> stones = [2,1,1,1]

- 2와 1을 고른다. -> 1은 파괴되고 2는 1이 된다. -> stones = [1,1,1]

- 1과 1을 고른다. -> 둘 다 파괴된다. -> stones = [1]

- 돌이 1개가 남았으므로 남은 돌의 무게인 1을 반환한다.

 

5. Code

1) 첫 코드(2023/06/07)

class Solution {
    public int lastStoneWeight(int[] stones) {
        Arrays.sort(stones);
        int i = stones.length-1;
        while(i>0){
            if(stones[i]==stones[i-1]){
                stones[i-1] = 0;
                i -= 2;
            } else{
                stones[i-1] = Math.abs(stones[i]-stones[i-1]);
                i--;
                sort(stones, i);
            }            
        }
        return stones[0];
    }

    static void sort(int[] arr, int i){
        while(i>0 && arr[i-1]>arr[i]){
            int tmp = arr[i];
            arr[i] = arr[i-1];
            arr[i-1] = tmp;
            i--;
        }
    }
}

- 98%, 56%

 

2) 힙을 이용해 본 코드(2023/06/08)

class Solution {
    public int lastStoneWeight(int[] stones) {
        heapsort(stones);
        int n = stones.length;
        while(--n>0 && stones[0]>0){     
            if(stones[0]==stones[1]){
                stones[0] = 0;
                stones[1] = 0;                
            } else{
                stones[0] -= stones[1];
                stones[1] = 0;
            }
            heapsort(stones);
        }
        return stones[0];
    }

    static void heapsort(int[] heap){
        for(int i=1 ; i<heap.length ; i++) {
            int c = i;
            while(c!=0) {
                int root = (c-1)/2;
                if(heap[root]<heap[c]) {
                    int tmp = heap[root];
                    heap[root] = heap[c];
                    heap[c] = tmp;
                }
                c = root;
            }
        }
        if(heap.length>2 && heap[1]<heap[2]){
            int tmp = heap[1];
            heap[1] = heap[2];
            heap[2] = tmp;
        }
    }
}

- 98%, 43%

- 1번이 메모리 절약이 더 된다. 아마 코드 맨 처음에 정렬하고 나서부터는 1번 풀이가 두 돌을 부딪친 후 남은 값이 제자리를 찾아가는 데 더 연산이 적어서 그런 것 같다.