[Leetcode]948. Bag of Tokens

문제 요약

• 알고리즘 분류:  그리디, 투 포인터
• 난이도: Medium
• 문제내용:
  • 초기 에너지(initial power)와 초기 점수(initial score) 0을 가지고 게임을 시작한다.
  • 수 배열 tokens가 주어지며, 이 배열의 tokens[i]는 각 토큰의 에너지 값을 나타낸다.
  • 각 토큰은 한 번만 사용할 수 있으며, 다음 두 가지 방법 중 하나로 사용할 수 있습니다
    • 앞면: 현재 에너지가 tokens[i] 이상인 경우, 토큰 tokens[i]를 사용하여 에너지를 tokens[i]만큼 잃고 점수를 1 증가시킬 수 있습니다.
    • 뒷면: 현재 점수가 1 이상인 경우, 토큰 tokens[i]를 사용하여 점수를 1 잃고 에너지를 tokens[i]만큼 얻을 수 있습니다.
  • 최대 점수를 반환 하여라
• 사이트 주소: https://leetcode.com/problems/bag-of-tokens/description/

문제풀이

 이번 문제는 그리디와 투 포인터를 황용한 문제이다. 그리디와 투 포인터 대한 개념은 아래 글을 보면 된다.

그리디: https://jih3508.tistory.com/70

[알고리즘 이론] 그리디(Greedy)

 투 포인터 : https://jih3508.tistory.com/235

[알고리즘 이론] 투 포인터(Two Pointers)

문제 접근 방법

 이번 문제는 그리디와 투 포인터를 동시에 활용해서 아이디어가 필요 하다. 그래서 어떻게 접근 해야 하는지 봐야 한다.

일단 아래 그림을 보자

 

위 순서대로 순차적으로 처리 하면  최대 2점을 얻을수 있다, 하지만 최대  점수를 얻기 위해서는 모든 경우의 수를 구하면 답은 구할수 있지만 효율적으로 구하기 위해서는 다른 방법으로 구해야 한다. 그러기 위해서는 Token을 정렬한 다음 작은에너지에서 점수얻고 큰 에너지에서는 점수 읽고 큰 에너지를 얻는 방식으로 가야 한다. 그러기 위해서는 아래와 같이 구현 하면된다.

1. Tokens를 정렬한다.
2. tokens를 0번째 인덱스를 start두고 tokens크기 -1를 end로 둔다.
3. 아래와 조건에따라 start가 end보다 클 때까지 처리 한다.
   1. 1. 현재 에너지가 start 위치 tokens 에너지 보다 클 경우에는 현재 에너지가 start위치 tokens에너지 차감하고 점수 +1시킨 다음 start위치를 다음 인덱스를 위치한다.
      2. 현재 에너지가 start 위치 tokens 에너지 보다 작을 경우에는 점수가 0일 경우에는 0으로 반환한다.
      3. 현재 에너지가 start 위치 tokens 에너지 보다 작을 경우에는 점수가 0보다 클 경우에는 점수 -1로 시키고 현재 점수에서 end위치 token에너지를 증가 시킨다.
4.  기록한 점수중 가장 큰것을 출력한다.

전체적으로는 grid알고리즘이 적용이 되었고 3번에서는 two pointer 알고리즘이 적용이 되었다. 

그래도 위와 같이 설명 했을때 이해가 안될수 있어서 이해가 되도록 위 예제 가지고 어떻게 돌아가는지 설명 하겠다.

1. tokens를 정렬 시키도 0번째 인덱스를 start 마지막 위치를 end로 둔다.

2.  start를 위치가 100보다 크기 때문에 100을 감소시키고 점수 +1 한다음 start위치를 다음 위치로 이동 시킨다.

3. start를 위치가 200보다 작기 때문에 점수 -1한 다음,  end위치한 에너지를 1000만큼 증가시키고 end 위치를 전 인덱스 위치로 이동 시킨다.

 

4. 200부터 400까지  token 에너지보다 크기 때문에  400까지 에너지 차감 시키고 계속 점수를 올린다.

5. 500보다 작기 때문에 end 위치 에너지를 가져 오고 500에너지를 차감한다. 그리고 start가 end보다 크기 때문에 종료 시킨다.

6.  기록한 점수중 가장 큰 것을 반환 한다. 그러면 답이 3이 나온다.

마무리

 이렇게 구현 했을때 나오는 시간 복잡도는 O(NlogN)이다. 그 이유는 정렬 시간 복잡도는  O(NlogN)이고 tow pointer에서는 O(N)만큼 나오는데 그 중 시간 복잡도에서 많이 나오는 것은 정렬이다. 그래서 시간 복잡도는 O(NlogN)이다.

 

Code

Python

from typing import List

class Solution:
    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:

        size = len(tokens)
        # 크기가 0이면 0으로 리턴
        if(size == 0):
            return 0

        start = 0
        end = size - 1
        score = 0
        scores = [0] * size
        tokens.sort()
        # two pointer
        while(start <= end):
            # power가 start 위치 token 값보다 클때  에너지를 감소하고 점수 1 증가
            if(power >= tokens[start]):
                power -= tokens[start]
                score += 1
                scores[start] = score
                start += 1
            else:
                # 현재 점수가 0보다 클때 점수 1로 감소하고 에너지를 증가
                if(score > 0):
                    power += tokens[end]
                    score -= 1
                    scores[end] = score
                    end -= 1
                # 현재 점수가 0이면 더이상 감소 시킬수 없어서 0으로 리턴 시킨다.
                else:
                    return 0
        # 기록 된 점수 값중 가장 큰 값을 출력한다.
        return max(scores)

Java

class Solution {
    public int bagOfTokensScore(int[] tokens, int power) {
       int size = tokens.length;

        // 크기가 0이면 0으로 리턴
        if(size == 0){
            return  0;
        }

        int score = 0;
        int[] scores = new int[size];
        Arrays.sort(tokens);
        int start = 0;
        int end = size - 1;
        // two pointer
        while (start <= end){
            //power가 start 위치 token 값보다 클때  에너지를 감소하고 점수 1 증가
            if(power >= tokens[start]){
                score++;
                power -= tokens[start];
                scores[start++] = score;
            }else{
                // 현재 점수가 0보다 클때 점수 1로 감소하고 에너지를 증가
                if(score > 0){
                    score -= 1;
                    power += tokens[end];
                    scores[end--] = score;
                }
                // 현재 점수가 0이면 더이상 감소 시킬수 없어서 0으로 리턴 시킨다.
                else{
                    return  0;
                }
            }
        }

        // 기록 된 점수 값중 가장 큰 값을 출력한다.
        return Arrays.stream(scores).max().getAsInt();
    }
}