[LeetCode] Java - Last Stone Weight

12일차 Last Stone Weight 입니다.

 

-문제 :

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

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 <= stones.length <= 30
1 <= stones[i] <= 1000

 

- 풀이 : 

class Solution {
    public int lastStoneWeight(int[] stones) {
		Arrays.sort(stones);
		
		int count = stones.length-1;
		while(count >= 1) {
			int cal = stones[count] - stones[count-1];
			if(cal == 0) {
				stones[count--] = 0; 
				stones[count--] = 0; 
			}else {
				stones[count--] = 0;
				stones[count] = cal;
			}
			Arrays.sort(stones, 0, count+1);
		}
		
        return stones[0];
    }
}

가장 큰 두 수를 빼고 남으면 다시 배열에 넣고 아니면 넣지 제거하는 문제입니다.

처음에는 다른 방식으로 생각해보았는데 이 방법이 가장 빠를 것 같아 풀어보니 통과했네요.

 

정렬과 stone의 계산된 수가 0일 때와 아닐 때를 구분하여 계산하는 방법입니다.

count와 stones를 정렬하는 방법으로 숫자가 한 개 남을 때까지 계산하는 방법입니다.

 

count는 stone의 개수를 저장하고 가장 무거운 스톤 두 개를 계산한 값이 0일 때와 아닐 때를 따로 계산합니다.

0이라면 두 수 모두 0으로 변경하고 아니라면 마지막 수만 0으로 다른 수는 두 수의 차를 저장합니다.

 

그리고 정렬을 다시 하고 반복합니다.

 

주어진 숫자가 1000가 최대 이기 때문에 시간 복잡도는 최대 O(n^2)이 아닐까 생각됩니다.