leetcode - Last Stone Weight

 

List<int>를 인자로 받습니다.

이것은 각 돌멩이들의 무게입니다.

 

돌멩이들은 서로 부딪혀 작은 돌멩이로 만들 수 있습니다.

 

만약 7 돌멩이와 8돌멩이가 부딪히면 1 돌멩이로 되고, 7 돌멩이와 7 돌멩이가 부딪히면 두개는 사라집니다.

 

이런 규칙에서, 남은 돌멩이의 최소 무게를 구해야 합니다.

 

논리적으로는 돌멩이 무게가 큰것들끼리 서로 부딪히게 해서 무게를 줄여나가야 합니다.

그렇기 때문에, 저는 아래와 같이 풀었습니다.

 

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        sorted_stones = sorted(stones, reverse=True)
        for i in range(len(stones) -1):
            if sorted_stones[0] == sorted_stones[1]:
                sorted_stones[0] = 0
                sorted_stones[1] = 0
            else:
                sorted_stones[1] = sorted_stones[0] - sorted_stones[1]
                sorted_stones[0] = 0
            sorted_stones = sorted(sorted_stones, reverse=True)
        return sum(sorted_stones)

 

 

부딪히는 횟수는 최대 돌멩이 갯수 -1 입니다.
이유로는, 최소가 되려면 어찌됐든 한번씩은 부딪혀야 하기 때문입니다.

 

 

• 무게가 큰 순으로 정렬시킵니다.
• 정렬했기 때문에 첫번째와 두번째만 비교합니다.
  
  • 무게가 같다면 둘다 사라지기 때문에 첫번째, 두번째 자리의 값을 0으로 넣습니다.
  • 무게가 같지 않다면, 첫번째자리에는 0, 두번째자리에는 그 차이값을 넣습니다.
• 무게가 큰것들끼리만 부딪혀야 최소가 나오기 때문에, 마지막으로 다시 정렬시켜 반복되도록 합니다.

감사합니다.