[LeetCode] Last Stone Weight

1.문제

You are given an array of integers stones where stones[i] is the weight of the ith stone.

We are playing a game with the stones. On each turn, we choose the heaviest two stones and smash them together. Suppose the heaviest two stones have weights x and y with x <= y. The result of this smash is:

• If x == y, both stones are destroyed, and
• If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x.
  At the end of the game, there is at most one stone left.

Return the weight of the last remaining stone. If there are no stones left, return 0.

stones 배열이 주어지고 i인덱스의 숫자는 i번째 stone의 무게라고 한다.

가장 큰 stone 두개를 선택했을 때 크기 비교를 하여 그 차이만큼 다시 배열에 들어간다고 할 때

마지막에 하나 남는 stone의 무게를 리턴하는 문제이다. 만약 남는 stone이 없다면 0을 리턴한다.

Example 1

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

Example 2

Input: stones = [1]
Output: 1

Constraints:

• 1 <= stones.length <= 30
• 1 <= stones[i] <= 1000

2.풀이

1. 우선 stones 를 내림차순 정렬한다.
2. 제일 앞에서부터 두 돌이 y , x 이므로 가장 앞의 두 숫자만 다루면 된다.
3. 두 돌을 비교하여 만약 크기가 다르면 그 차이를 배열에 넣어주고 다시 내림차순 정렬한다.
4. 위 과정을 stones.length <= 1 이 될때까지 반복한다.

/**
 * @param {number[]} stones
 * @return {number}
 */
const lastStoneWeight = function (stones) {
  stones.sort((a, b) => b - a); //내림차순 정렬하기

  while (true) {
    if (stones.length <= 1) {
      // 배열의 길이가 1 미만이면
      return stones.length === 1 ? stones[0] : 0; //배열에 stone이 남아있으면 남은 stone 리턴
    } else {
      let y = stones.shift(); // y stone
      let x = stones.shift(); // x stone

      if (y !== x) {
        // y stone 이 x stone 보다 무거우면
        stones.unshift(y - x); // 그 차이를 배열 앞에 삽입
        stones.sort((a, b) => b - a); // 다시 내림차순으로 정렬
      }
    }
  }
};

3.결과