파이썬의 마지막 돌 무게

<시간/>

암석이 있다고 가정하고 각 암석에는 양의 정수 가중치가 있습니다. 매 턴마다 우리는 가장 무거운 돌 두 개를 가져다가 함께 부술 것입니다. 돌에 가중치 x와 y가 있고 x <=y가 있다고 가정합니다. 이 스매시의 결과는 두 가지 유형이 될 수 있습니다.

x =y이면 두 돌이 완전히 파괴됩니다.
그렇지 않으면 x !=y일 때 무게 x의 돌은 완전히 파괴되고 무게 y의 돌은 새로운 무게 y-x를 갖습니다.

마지막으로 최대 1개의 스톤이 남아 있습니다. 이 돌의 무게를 구해야 합니다. (돌이 없을 때는 0입니다.)

따라서 돌 무게가 [2,7,4,1,8,1]이면 결과는 1이 됩니다. 먼저 7과 8을 선택한 다음 1을 얻으므로 배열은 [2,4,1,1]이 됩니다. ,1], 두 번째로 2와 4를 선택합니다. 배열은 [2,1,1,1]이 되고 2와 1을 선택한 후 배열은 [1,1,1]이 되고 가중치가 1인 두 개의 돌을 선택하고 그러면 둘 다 파괴되므로 배열은 [1]이 됩니다. 이것이 답입니다

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

돌 가중치 배열 W에 요소가 없으면 0을 반환합니다.
W에 요소가 하나만 있으면 W[0]을 반환합니다.
W가 둘 이상의 요소를 갖는 동안 -
- W 정렬
- s1 :=W의 마지막 요소, s2 :=W의 두 번째 마지막 요소
- s1 =s2이면 W에서 s1과 s2를 제거합니다.
- 그렇지 않으면 s1 :=|s1 – s2|, W에서 마지막 요소를 제거한 다음 s1을 W의 마지막 요소로 설정
W에 하나의 요소가 있으면 해당 요소를 반환하고, 그렇지 않으면 0을 반환합니다.

예

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

class Solution(object):
   def lastStoneWeight(self, stones):
      """
      :type stones: List[int]
      :rtype: int
      """
      if len(stones) ==0:
         return 0
      if len(stones) == 1:
         return 1
      while len(stones)>1:
         stones.sort()
         s1,s2=stones[-1],stones[-2]
         if s1==s2:
            stones.pop(-1)
            stones.pop(-1)
         else:
            s1 = abs(s1-s2)
            stones.pop(-1)
            stones[-1] = s1
      if len(stones):
         return stones[-1]
      return 0
ob1 = Solution()
print(ob1.lastStoneWeight([2,7,4,1,6,1]))

입력

[2,7,4,1,6,1]

파이썬의 마지막 돌 무게

예

입력

출력