🔥 다트 🔥 토큰 백 || 리트코드 || 쉽고 간단한 솔루션 || 100% 더 빠른 코드 || 한 줄씩 설명

솔루션 - 1 정렬

class Solution {
//   Time Complexity : O(nlogn)
//   Space Complexity : O(1)
// Runtime: 336 ms, faster than 100.00% of Dart online submissions for Bag of Tokens.
// Memory Usage: 158.9 MB, less than 100.00% of Dart online submissions for Bag of Tokens.

  int bagOfTokensScore(List<int> tokens, int power) {
    // length of the tokens
    int n = tokens.length;
    // if the length is zero we will return zero because it empty
    if (n == 0) return 0;
    // sorting tokens smallest to largest
    tokens.sort();
    // holding the value of the inside list
    int value = 0;
    //index of tokens inside tokens list
    int index = n - 1;
    // value to hold the current score
    int currentScore = 0;
    // value to hold max score
    int maxScore = 0;
    // assuming that our value is less than and equal the idex
    while (value <= index) {
      // for example power is greater than tokens value
      if (power >= tokens[value]) {
        // than we will subtract the power from the token value
        power -= tokens[value];
        // and we will increment the current score
        currentScore++;
        // for example if current score is greater than max score than
        // our max score will be current score and than we will increment the value
        if (currentScore > maxScore) maxScore = currentScore;
        value++;
        // for example if current score is just greater than 1 point

      } else if (currentScore >= 1) {
        // than we will increment the value of power with based on
        //  the value which is available at index point
        power += tokens[index];
        // we decrement the index value
        index--;
        // and also current score
        currentScore--;
      } else
     // breaking because we can't play anymore
        break;
    }
    // return the total max score
    return maxScore;
  }
}

솔루션 - 2개의 두 포인터 솔루션

설명

우리는 이 문제를 두 포인터 접근법을 사용하여 풀 수 있습니다!

직관 :

토큰 목록을 정렬합니다.
포인터 i는 처음에 목록의 시작 부분을 가리킵니다. (점수를 얻기 위해 소비하는 데 필요한 가장 낮은 전력으로 점수에 추가됨)
포인터 j는 처음에 목록의 끝을 가리킵니다. (점수에서 단 한 점만 사용하여 얻을 수 있는 가장 큰 힘)
왜 욕심?

우리는 항상 점수를 높이는 경향이 있습니다. 따라서 충분한 파워가 있을 때까지 현재 파워에서 파워(tokens[i])를 빼서 i를 계속 증가시키고 매번 점수에 단일 포인트를 추가합니다.

우리에게 충분한 힘이 없을 때, 우리는 우리가 할 수 있는 최소한의 점수인 1점만 소비함으로써 토큰 배열에서 최대 힘을 ​​얻으려고 노력할 것입니다. 이제 현재 점수에서 1점을 빼고 파워(토큰[j])를 현재 파워에 더하고 j를 1씩 줄입니다.

토큰 목록에서 적어도 하나의 포인트를 더 얻을 것이라고 확신하는 경우에만 점수에서 단일 포인트를 사용하게 된다는 점을 기억하십시오. 그렇지 않으면 토큰을 사용하지 않아도 됩니다. 간접적으로 다음 시나리오를 의미합니다.

당신은 힘이 없습니다. 배열에는 하나의 요소만 남습니다. 당신의 현재 점수는 >= 1입니다. 이런 상황에서 토큰을 플레이하고 권력을 얻는 데 점수의 1점을 소비하더라도 아무 소용이 없겠죠? 우리는 아무 이득도 없이 우리의 한 점을 낭비하고 있을 뿐입니다!!

class Solution {
// Runtime: 653 ms, faster than 100.00% of Dart online submissions for Bag of Tokens.
// Memory Usage: 147.6 MB, less than 100.00% of Dart online submissions for Bag of Tokens.

  int bagOfTokensScore(List<int> tokens, int power) {
    int scores = 0;
    int s = 0, e = tokens.length - 1;
    tokens.sort((a, b) => a - b);
    if (e + 1 == 0 || power < tokens[0]) return 0;
    while (s <= e) {
      if (power >= tokens[s]) {
        scores++;
        power -= tokens[s++];
      } else {
        if (e - s >= 1) {
          power += tokens[e--];
          scores--;
        } else
          break;
      }
    }
    return scores;
  }
}

솔루션 - 3

class Solution {
// Runtime: 607 ms, faster than 100.00% of Dart online submissions for Bag of Tokens.
// Memory Usage: 148 MB, less than 100.00% of Dart online submissions for Bag of Tokens.
  int bagOfTokensScore(List<int> tokens, int power) {
    // play i-th token face up -> lose tokens[i] power -> choose the smallest one
    // play i-th token face down -> gain tokens[i] power -> choose the largest one
    // hence, sort tokens first
    tokens.sort();
    // two pointes - l for tracking face up & r for tracking face down
    int l = 0, r = tokens.length - 1;
    int currentScore = 0, maxScore = 0;
    while (l <= r) {
      // there are 3 cases
      if (tokens[l] <= power) {
        // case 1. play l-th tokens face up if its power <= the current power
        // ---
        // losing tokens[l] power
        power -= tokens[l];
        // and gaining 1 score
        currentScore += 1;
        // cur_score can be mx_score potentially
        maxScore = max(maxScore, currentScore);
        // move the pointer to the right
        l += 1;
      } else if (currentScore >= 1) {
        // case 2. play r-th tokens face down if the current score is at least 1
        // ---
        // gaining tokens[r] power
        power += tokens[r];
        // and losing 1 score
        currentScore -= 1;
        // move the pointer to the left
        r -= 1;
      } else {
        // case 3. impossible to play
        // ---
        // either you don't enough power or enough score
        break;
      }
    }
    return maxScore;
  }
}

보너스 솔루션 - Golang 100% 빨라짐

package main

import "sort"

func bagOfTokensScore(tokens []int, P int) int {
 // to hold the value  of our score
 var score int = 0
 // sorting the token and slicing because sort.slice is more stable
 sort.Slice(tokens, func(i, j int) bool { return tokens[i] < tokens[j] })
 // loop if the token length is greater than 0 abd power is also greater and equal
 // than the first value of the token list
 for len(tokens) > 0 && P >= tokens[0] {
  // we will decrement the first value of token from the power
  P = P - tokens[0]
  // increment the score because we point a score
  score++
  tokens = tokens[1:]
  // if the length of the list of tokens is more than 1 and power is less than first value of the list
  if len(tokens) > 1 && P < tokens[0] {
   // than we will increment the value of power inside the first index of the token
   P = P + tokens[len(tokens)-1]
   // we will decrement the score
   score--
   tokens = tokens[:len(tokens)-1]
  }
 }
 // than we will total score we have achieved
 return score
}