[Leetcode] Last Stone Weight (#1046)

 

 

문제 

 

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 smallest possible weight of the left stone. If there are no stones left, return 0.

 

 

입출력 

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.

 

 

해설 코드 

class Solution(object):
    def lastStoneWeight(self, stones):
        stones.sort(reverse=True)
        
        while (len(stones) > 1):
            # 배열 내 가장 큰 수와 두 번째로 큰 수는 계속 없앤다
            heaviest = max(stones)
            stones.remove(heaviest)
            heavier = max(stones)
            stones.remove(heavier)
            # 두 수가 다를 때만 두 수의 차를 append 해준다
            if heaviest != heavier:
                stones.append(heaviest - heavier)
        if len(stones) == 0:
            return 0
        else:
            return stones[0]

분석 > 문제의 원리는 간단하다. 배열의 길이가 1 보다 클 때까지 배열 내 가장 큰 수와 두 번째로 큰 수를 없애고 두 수가 다를 때만 두 수의 차를 append해준다. 마지막으로 배열의 길이가 0이 된다면 0을 반환하고 나머지는 배열 내에 남아있는 값을 반환하면 된다. 

 

 

고찰 

이 문제를 풀 때 생각보다 난항을 겪었는데, 그 이유는 문제의 진행 사항을 예시대로 정확하게 표현하는 데에만 집중했기 때문이다. 그러다 보니 중간에 코드가 자주 꼬였다. 이러한 과정을 겪으면서 문제를 풀 때 중요한 부분은 문제를 어떻게 단순한 원리로 치환하는 것이라는 생각이 들었다.