Last Stone Weight
-
1046. Last Stone WeightAlgorithm/LeetCode 2020. 5. 31. 11:15
출처: leetcode.com/problems/last-stone-weight/ 분류: Greedy, Easy 접근방식 무게가 가장 큰 돌과 그 다음으로 큰 돌을 부시면서 1개의 돌이 남을 때까지 반복하는 문제 입니다. 두 돌의 무게가 같다면 그대로 없어지고 한쪽이 더 크다면 그 나머지가 다시 남은 돌이 됩니다. 문제는 두 돌을 골라서 부실 때마다 돌의 우선순위가 바뀐다는 점입니다. 즉, 매 스탭마다 가장 큰 돌이 바뀔 수 있다는 점이죠. 이 점을 잘 체크하면 되는 문제입니다. 해결방법 단순하게 매 스탭마다 max를 2번 뽑아서 제거해주는 방법을 사용할 수도 있겠으나, swift 기준으로 max의 시간복잡도가 O(n) 이고 max의 인덱스를 찾는데 O(n), 이를 제거하는데 O(n) 의 시간이 소요됩니다..