1046. Last Stone Weight

출처: leetcode.com/problems/last-stone-weight/

분류: Greedy, Easy

---

접근방식

무게가 가장 큰 돌과 그 다음으로 큰 돌을 부시면서 1개의 돌이 남을 때까지 반복하는 문제 입니다. 
두 돌의 무게가 같다면 그대로 없어지고 한쪽이 더 크다면 그 나머지가 다시 남은 돌이 됩니다.
문제는 두 돌을 골라서 부실 때마다 돌의 우선순위가 바뀐다는 점입니다.

즉, 매 스탭마다 가장 큰 돌이 바뀔 수 있다는 점이죠. 이 점을 잘 체크하면 되는 문제입니다.

해결방법

단순하게 매 스탭마다 max를 2번 뽑아서 제거해주는 방법을 사용할 수도 있겠으나, 
swift 기준으로 max의 시간복잡도가 O(n) 이고 max의 인덱스를 찾는데 O(n), 이를 제거하는데 O(n) 의 시간이 소요됩니다.
매 스탭마다 이걸 2번씩 반복하는 꼴이 되니 별로 좋은 방법은 아니겠죠?

swift에서 sort의 시간 복잡도는 O(nlogn) 이고 배열에서 맨 앞이나 중간이 아닌 맨 뒤의 요소를 제거하는건 O(1)이면 되므로 이 둘을 이용했습니다. 배열의 길이가 1이 될 때까지, 오름차순으로 정렬하고 뒤에 2개를 가지고 계산하는 과정을 반복합니다.
이렇게 하면 O(n * nlogn)의 시간 복잡도로 해결할 수 있습니다. 

func lastStoneWeight(_ stones: [Int]) -> Int {
    var orderedStones = stones.sorted()

    while orderedStones.count > 1 {
        let m1 = orderedStones.removeLast()
        let m2 = orderedStones.removeLast()
        let remain = m1 - m2
        
        if remain != 0 {
            orderedStones.append(remain)
            orderedStones.sort()
        }
    }
    return orderedStones.isEmpty ? 0 : orderedStones[0]
}

 

회고

다른 분들의 풀이를 보니 힙을 사용하는 방법도 있었다.