leetcode : Bag of tokens

https://leetcode.com/problems/bag-of-tokens/submissions/

Bag of Tokens - LeetCode

power를 토큰i만큼 소비하면 스코어를 1 올릴 수 있고

스코어를 1소비하면 토큰i만큼의 power를 얻을 수 있다.

 

스코어의 증감이 한번에 1이라고 딱 고정되어있어서 목표는 명확해진다.

스코어를 소비해서 power를 얻을 땐 최대한 큰 power를 얻어야 효율적이고

power를 소비해서 스코어를 올릴땐 최대한 작은 power를 소비해서 얻어야 단가가 싸진다.

당연한 얘기다.

그래서 이건 greedy algorithm으로 분류될거같다.

 

문제 조건을 보면 꼭 모든 토큰을 다 쓸 필요는 없다고 하는데 이건 play를 하면서 정답값max를 계속 갱신해주는 방법으로 손쉽게 해결이 가능하다. 토큰들을 play하면서 스코어는 오르락 내리락 하는데 고점값을 기록하기만 하면 그게 정답이 되니까.

 

class Solution:
    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:
        score = 0
        answer = 0
        
        tokens.sort()
        
        left = 0
        right = len(tokens) - 1
        
        while left <= right and (tokens[left] <= power or score > 0):
            if tokens[left] <= power:
                score += 1
                power -= tokens[left]
                left += 1
            elif score > 0:
                score -= 1
                power += tokens[right]
                right -= 1
            answer = max(answer, score)
            
        return answer

 

공간복잡도는 무조건 O(1)이고

시간복잡도는 two pointers를 써서 각 토큰을 한번씩만 참조하니까 O(N)인데 정렬을 하니까 O(N log N)