[1스4코2파] # 235. LeetCode 1046. Last Stone Weight

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (235차)
[4코1파] 2023.01.13~ (227일차)
[1스4코1파] 2023.04.12~ (138일차)
[1스4코2파] 2023.05.03 ~ (116일차)

Today :

2023.08.26 [235일차]
1046. Last Stone Weight
https://leetcode.com/problems/last-stone-weight/

1046. Last Stone Weight

문제 설명

정수로 구성된 배열 stones가 주어질 때 배열을 구성하는 정수는 stones의 index에 해당하는 돌의 무게이다.
매 턴마다 가장 무거운 돌을 두개 선택해서 부시고, 가장 무거운 두 돌의 무게가 x,y 이면 x<=y라고 가정할 때, x==y이면 두 돌이 부셔지고 x!=y면 x인 돌만 파괴되고 y는 y-x가 됨 게임이 끝나면 최대 1개의 돌만 남을때 마지막 남은 돌의 무게를 반환하고, 남은 돌이 없으면 0을 반환함

문제 풀이 방법

maxHeap을 이용해서 풀면 시간 복잡도는 O(nlogn)가 걸리게 된다.

내 코드

import heapq

class Solution:
    def lastStoneWeight(self, stones: list[int]) -> int:
        stones = [-s for s in stones]
        heapq.heapify(stones)

        while len(stones) >1:
            first = heapq.heappop(stones)
            second = heapq.heappop(stones)
            if second > first:
                heapq.heappush(stones, first-second)

        stones.append(0) 
        return abs(stones[0])  

증빙

여담

마이너스로 넣어주는 버르장머리는 어디서 나온건지