LeetCode 솔루션 분류
[9/12] 948. Bag of Tokens
본문
948. Bag of Tokens
Medium
1611382Add to ListShareYou have an initial power of power, an initial score of 0, and a bag of tokens where tokens[i] is the value of the ith token (0-indexed).
Your goal is to maximize your total score by potentially playing each token in one of two ways:
- If your current power is at least
tokens[i], you may play theithtoken face up, losingtokens[i]power and gaining1score. - If your current score is at least
1, you may play theithtoken face down, gainingtokens[i]power and losing1score.
Each token may be played at most once and in any order. You do not have to play all the tokens.
Return the largest possible score you can achieve after playing any number of tokens.
Example 1:
Input: tokens = [100], power = 50 Output: 0 Explanation: Playing the only token in the bag is impossible because you either have too little power or too little score.
Example 2:
Input: tokens = [100,200], power = 150 Output: 1 Explanation: Play the 0th token (100) face up, your power becomes 50 and score becomes 1. There is no need to play the 1st token since you cannot play it face up to add to your score.
Example 3:
Input: tokens = [100,200,300,400], power = 200 Output: 2 Explanation: Play the tokens in this order to get a score of 2: 1. Play the 0th token (100) face up, your power becomes 100 and score becomes 1. 2. Play the 3rd token (400) face down, your power becomes 500 and score becomes 0. 3. Play the 1st token (200) face up, your power becomes 300 and score becomes 1. 4. Play the 2nd token (300) face up, your power becomes 0 and score becomes 2.
Constraints:
0 <= tokens.length <= 10000 <= tokens[i], power < 104
Accepted
73,751
Submissions
145,377
관련자료
-
링크
댓글 1
학부유학생님의 댓글
- 익명
- 작성일
Runtime: 64 ms, faster than 84.91% of Python3 online submissions for Bag of Tokens.
Memory Usage: 14.1 MB, less than 7.08% of Python3 online submissions for Bag of Tokens.
Memory Usage: 14.1 MB, less than 7.08% of Python3 online submissions for Bag of Tokens.
from collections import deque
class Solution:
def bagOfTokensScore(self, tokens: List[int], power: int) -> int:
score = max_score = 0
tokens = deque(sorted(tokens))
while tokens:
# gain score
if power >= tokens[0]:
power -= tokens.popleft()
score += 1
# gain power by consuming score
else:
if not score: break
score -= 1
power += tokens.pop()
max_score = max(max_score, score)
return max_score
