LeetCode 솔루션 분류
1046. Last Stone Weight
본문
[ LeetCode 시즌 3 ] 2022년 4월 7일 문제 입니다.
[Easy] 1046. Last Stone Weight
https://leetcode.com/problems/last-stone-weight/
[Easy] 1046. Last Stone Weight
You are given an array of integers stones where stones[i] is the weight of the ith stone.
We are playing a game with the stones. On each turn, we choose the heaviest two stones and smash them together. Suppose the heaviest two stones have weights x and y with x <= y. The result of this smash is:
- If
x == y, both stones are destroyed, and - If
x != y, the stone of weightxis destroyed, and the stone of weightyhas new weighty - x.
At the end of the game, there is at most one stone left.
Return the smallest possible weight of the left stone. If there are no stones left, return 0.
Example 1:
Input: stones = [2,7,4,1,8,1] Output: 1 Explanation: We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then, we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then, we combine 2 and 1 to get 1 so the array converts to [1,1,1] then, we combine 1 and 1 to get 0 so the array converts to [1] then that's the value of the last stone.
Example 2:
Input: stones = [1] Output: 1
Constraints:
1 <= stones.length <= 301 <= stones[i] <= 1000
https://leetcode.com/problems/last-stone-weight/
관련자료
-
링크
댓글 7
EuroCha님의 댓글
- 익명
- 작성일
초보자라 더럽지만..! Daily Check!
Python3 구요
Python3 구요
def lastStoneWeight(self, stones: List[int]) -> int:
stones.sort()
length_of_stones = len(stones)
while length_of_stones > 1:
if(stones[length_of_stones-1] > stones[length_of_stones-2]):
new_stone_to_push = stones[length_of_stones-1]-stones[length_of_stones-2]
stones.pop(length_of_stones-1)
stones.pop(length_of_stones-2)
stones.append(new_stone_to_push)
length_of_stones -= 1
stones.sort()
else:
stones.pop(length_of_stones-1)
stones.pop(length_of_stones-2)
length_of_stones -= 2
if(len(stones)>=1):
return stones[0]
else:
return 0mingki님의 댓글
- 익명
- 작성일
C++ 솔루션입니다
class Solution {
public:
int lastStoneWeight(vector<int>& stones) {
multiset<int, std::greater<int>> s(stones.begin(), stones.end());
while (s.size() > 1) {
int s1 = *s.begin(); s.erase(s.begin());
int s2 = *s.begin(); s.erase(s.begin());
int res = abs(s1 - s2);
if (res > 0) {
s.insert(res);
}
}
return s.empty() ? 0 : *s.begin();
}
};CANUS님의 댓글
- 익명
- 작성일
Swift version 입니다. 역시 초보자로서 도전해봤습니다.
class Solution {
func lastStoneWeight(_ stones: [Int]) -> Int {
guard stones.count > 1 else { return stones[0] }
if stones.count == 2, Set(stones).count == 1 {
return 0
}
var mutableStones = stones
let sorted = mutableStones.sorted { $0 > $1 }
let first = sorted[0]
let second = sorted[1]
if first == second, let idx0 = mutableStones.firstIndex(of: first) {
mutableStones.remove(at: idx0)
let idx1 = mutableStones.firstIndex(of: second)!
mutableStones.remove(at: idx1)
} else if first > second {
let idx0 = mutableStones.firstIndex(of: first)!
mutableStones[idx0] = first - second
let idx1 = mutableStones.firstIndex(of: second)!
mutableStones.remove(at: idx1)
} else {
let idx1 = mutableStones.firstIndex(of: second)!
mutableStones[idx1] = second - first
let idx0 = mutableStones.firstIndex(of: first)!
mutableStones.remove(at: idx0)
}
return lastStoneWeight(mutableStones)
}
}핸디맨님의 댓글
- 익명
- 작성일
# O(N^2 logN) time | O(N) space
class Solution:
def lastStoneWeight(self, stones: List[int]) -> int:
while len(stones) > 1:
stones.sort()
firstRock = stones.pop()
secondRock = stones.pop()
if firstRock == secondRock:
if len(stones) == 0:
return 0
else:
continue
else:
newStone = firstRock-secondRock
stones.insert(0,newStone)
return stones[0]bobkim님의 댓글
- 익명
- 작성일
class Solution {
public:
int lastStoneWeight(vector<int>& stones) {
int max=0;
int xIndex=-1, yIndex=-1;
while( stones.size() > 1 ){
for(int i=0;i<stones.size();i++){
if(i==1){
if(stones[1]<max){
xIndex=1;
};
};
if(stones[i]>=max){
xIndex=yIndex;
max=stones[i];
yIndex=i;
}else{
if(stones[i]>stones[xIndex])
xIndex=i;
};
};
if((stones[xIndex] == stones[yIndex])&&( xIndex != yIndex )){
if(stones.size()==2){
stones.pop_back();
stones.pop_back();
}else{
if(xIndex>yIndex){
stones.erase(stones.begin()+xIndex);
stones.erase(stones.begin()+yIndex);
}else{
stones.erase(stones.begin()+yIndex);
stones.erase(stones.begin()+xIndex);
};
};
max=0;
xIndex=yIndex=-1;
}else{
stones[yIndex]=stones[yIndex]-stones[xIndex];
stones.erase(stones.begin() + xIndex);
max=0;
xIndex=yIndex=-1;
};
};
if(!stones.empty()){
return stones[0];
}else{
return 0;
};
};
};9dea0936님의 댓글
- 익명
- 작성일
import heapq
class Solution:
def lastStoneWeight(self, stones: List[int]) -> int:
heap = []
for i in stones:
heapq.heappush(heap, -1 * i)
while len(heap) != 1:
a = heapq.heappop(heap) * -1
b = heapq.heappop(heap) * -1
heapq.heappush(heap, abs(a - b) * -1)
return heapq.heappop(heap) * -1Jack님의 댓글
- 익명
- 작성일
https://github.com/JackKimUSA/leetcode-python-solutions
Python3
Submissions:
- Runtime: 28 ms, faster than 96.66% of Python3 online submissions for Last Stone Weight.
- Memory Usage: 13.9 MB, less than 17.99% of Python3 online submissions for Last Stone Weight.
Python3
Submissions:
- Runtime: 28 ms, faster than 96.66% of Python3 online submissions for Last Stone Weight.
- Memory Usage: 13.9 MB, less than 17.99% of Python3 online submissions for Last Stone Weight.
class Solution:
def lastStoneWeight(self, stones: List[int]) -> int:
for i in range(len(stones)):
stones[i] *= -1
heapq.heapify(stones)
while len(stones) > 1:
stone1=heapq.heappop(stones)
stone2=heapq.heappop(stones)
if stone1 != stone2:
heapq.heappush(stones,(stone1-stone2))
return -heapq.heappop(stones) if stones else 0
