[2024] day 65. Leetcode 948. Bag of Tokens
코딩테스트
2024년부터 새롭게 다시 시작하는 코딩테스트
2024년 3월 4일 (월)
Leetcode daily problem
948. Bag of Tokens
https://leetcode.com/problems/bag-of-tokens/description/?envType=daily-question&envId=2024-03-04
Problem
정수 배열 tokens와 초기 score 0, 초기 파워가 주어질 때, 토큰을 전략적으로 플레이하여 총 점수를 최대화하는 것이다 .
하나의 토큰은 아래의 두 가지 방법 중 하나만 수행할 수 있다.
토큰을 사용하는 방법은
(1) face-up : 토큰을 하나 사용해서 점수를 1만큼 올리기
현재 power가 tokens[i] 이상이면 tokens[i] power를 잃고 1점을 얻을 수 있음
(2) face-down : 점수를 하나 잃고 토큰을 하나 사용하여 점수를 1만큼 올리기
현재 점수가 1점 이상인 경우 tokens[i] power를 얻고 1점을 잃음
원하는 만큼의 토큰을 플레이한 후 얻을 수 있는 최대 가능한 점수를 반환한다.
Solution
greedy, game theory, (or queue)
해당 문제는 게임이론과 그리디 알고리즘을 활용해서 해결할 수 있다. 주어진 토큰을 사용해서 점수를 최대화 하는 것이다.
백팩에 정수 값으로 표현된 일정한 양의 토큰이 있고,
한번에 한 개 이상의 토큰을 사용할 수 있다.
토큰을 사용하는 방법은
(1) face-up : 토큰을 하나 사용해서 점수를 1만큼 올리기
(2) face-down : 점수를 하나 잃고 토큰을 하나 사용하여 점수를 1만큼 올리기
이므로, 초기에 점수가 0이므로 face-down으로 점수를 음수로 만들 수 없다.
문제를 해결하기 위해서는 그리디 방법을 사용하는데,
토큰을 가장 작은 값부터 큰 값 순서로 정렬하고, 점수가 충분히 높아질 수록 최대한 많은 토큰을 점수로 바꾼다.
점수르 바꾸는 것을 멈춘 후에 점수를 교환한 후 최종 점수를 반환하낟.
이 때, 그리디 방법을 위해 왼쪽 인덱스와 오른쪽 인덱스를 정의하는데 왼쪽 인덱스는 토큰을 사용하는 과정 (face-up), 오른쪽 인덱스느 점수를 교환하는 (face-down) 과정이다.
왼쪽 인덱스가 오른쪽 인덱스보다 작거나 같을 때 까지 아래의 과정을 반복한다.
- 현재 점수가 토큰을 사용할 수 있을 경우, 가장 작은 토큰을 사용해 점수를 증가시킨다. 점수와 토큰 사용 횟수를 업데이트 한다.
- 현재 점수가 토큰을 교환할 수 있는 경우, 가장 큰 토큰을 교환해 점수를 감소 시키고 토큰 사용 횟수를 갱신한다.
마지막 얻은 점수를 반환해서 최적의 선택을 해가면서 최대 점수를 얻는다.
Code
class Solution:
def bagOfTokensScore(self, tokens: List[int], power: int) -> int:
tokens.sort()
left, right = 0, len(tokens)-1
maxScore, curScore = 0,0
while left <= right:
if tokens[left] <= power:
curScore +=1
power -= tokens[left]
maxScore = max(maxScore, curScore)
left +=1
elif curScore > 0:
curScore -=1
power += tokens[right]
right -=1
else:
break
return maxScore
Complexicity
시간 복잡도
주어진 토큰을 정렬하는데 O(nlogn)이 소요되고,
그리디 알고리즘을 수행하면서 토큰을 한 번씩 사용하므로 각 토큰을 검사하는 O(n)이 소요된다.
전체적으로 시간 복잡도는 O(nlogn)이다.
공간 복잡도
주어진 토큰 배열을 정렬하기 위해 O(n) 이 필요하므로 공간복잡도는 O(n)이다.
