LeetCode1046. Last Stone Weight

1. 문제(원본)

We have a collection of rocks, each rock has a positive integer weight.

Each turn, we choose the two heaviest rocks 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.)

 

Example 1:

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.

 

Note:

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

2. 문제

입력된 정수형 배열에서 큰 값을 가진 두 개의 인덱스를 페어로 하여 뺄셈을 한다.

여기서 결과가 0이 된다면 두 수는 파괴하고, 0이 아닌 다른 수일 경우 작은 수는 파괴, 큰 수 쪽은 남은 값 만큼 유지한다.

3. 나의 답

class Solution {

    func lastStoneWeight(_ stones: [Int]) -> Int {

        var sorted = stones.sorted { $0 > $1 }

        while sorted.count > 1 {

            if sorted[0] == sorted[1] {

                sorted.removeSubrange(0...1)

            } else {

                sorted.append(abs(sorted[1] - sorted[0]))

                sorted.removeSubrange(0...1)

            }

            sorted = sorted.sorted { $0 > $1 }

            print(sorted)

        }

        return sorted.first ?? 0

    }

}

4. 다른 유저의 답

#1

class Solution {

    func lastStoneWeight(_ stones: [Int]) -> Int {

        var results = smash(stones)

        return results.count == 0 ? 0 : results.first!

    }

    

    func smash(_ stones: [Int]) -> [Int] {

        if stones.count <= 1 { return stones }

        

        var myStones = stones

        myStones.sort()

        var s1 = myStones.removeLast() // heaviest rock

        var s2 = myStones.removeLast() // second heaviest rock

        

        if s1 != s2 {

            myStones.append(s1 - s2)

        }

        

        return smash(myStones)

    }

}

5. 마무리

배열의 조작이 필요했지만 과정은 별로 중요한 것이 아니었던 문제였기 때문에 매번 정렬을 해주면서 큰 수를 앞으로 몰아 쉽게 페어를 이룰 수 있게 해보았다.