[LeetCode] 948. Bag of Tokens

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

Leetcode - Bag of Tokens

문제 유형 : 그리디, 투포인터, 정렬

문제 난이도 : Medium

 

문제

You start with an initial power of power, an initial score of 0, and a bag of tokens given as an integer array tokens, where each tokens[i] donates the value of tokeni.

Your goal is to maximize the total score by strategically playing these tokens. In one move, you can play an unplayed token in one of the two ways (but not both for the same token):

• Face-up: If your current power is at least tokens[i], you may play tokeni, losing tokens[i] power and gaining 1 score.
• Face-down: If your current score is at least 1, you may play tokeni, gaining tokens[i] power and losing 1 score.

Return the maximum possible score you can achieve after playing any number of tokens.

 

당신은 power만큼의 파워를 처음에 가지고, 점수는 0입니다.

토큰의 배열 tokens가 주어집니다.

당신의 목표는 토큰을 플레이하여 점수를 최대화하는 것입니다.

플레이하지 않은 토큰에 대해 다음의 행동을 할 수 있습니다:

• Face-up: 만약 현재 파워가 적어도 tokens[i]만큼 있다면, tokens[i]를 플레이하는 것이고, tokens[i]만큼의 파워를 잃고 1점을 얻습니다.
• Face-down: 만약 현재 점수가 적어도 1이면, tokens[i]를 플레이하는 것이고, tokens[i]만큼의 파워를 얻고 1점을 잃습니다.

 

tokens중 몇 개의 토큰을 플레이하여 얻는 최대 개수를 구하시오.(모든 토큰을 다 플레이할 필요는 없습니다)

 

풀이

Face-up과 Face-down의 규칙으로보아, Face-up은 작은 수로, Face-down은 큰 수로 플레이하는 것이 유리합니다.

오름차순으로 정렬하고, left = 0, right = n-1의 인덱스로 시작합니다.

우선 Face-up부터 가능한지 확인하고 가능하면 Face-up(left의 인덱스 증가), 안되면 Face-down이 가능한지 확인하고 가능하면 Face-down(right의 인덱스 감소).

둘다 안되면 반복문을 끝냅니다.

 

Face-Up을 하고나서는 최대 점수를 업데이트합니다. (꼭 다 플레이할 필요 없으므로 Face-Up마다 최대점수계산. 다 순회하는게 오히려 마이너스일 수 있다.)

 

코드

C++

class Solution {
public:
    int bagOfTokensScore(vector<int>& tokens, int power) {
        sort(tokens.begin(), tokens.end());
        const int n = tokens.size();
        int score = 0, maxScore = 0;
        int left = 0, right = n-1;

        while(left <= right) {
            // Face Up:
            if(power >= tokens[left]) {
                power -= tokens[left];
                left++;
                score++;
                maxScore = max(maxScore, score);
                continue;
            }

            // Face Down:
            if(score > 0) {
                power += tokens[right];
                right--;
                score--;
                continue;
            }

            break;
        }
        return maxScore;
    }
};