초기 파워 P와 초기 점수 0점, 그리고 하나의 토큰 가방이 주어져 있다고 가정해 보겠습니다. 각 토큰은 최대 한 번만 사용할 수 있으며, token[i]라는 고유한 값을 가지고 있습니다. 각 토큰은 다음 두 가지 방식으로 활용할 수 있습니다.
- 앞면으로 사용: 현재 파워가
token[i]이상이라면, 해당 토큰을 앞면으로 내려놓아token[i]만큼 파워를 잃는 대신 1점을 얻습니다. - 뒷면으로 사용: 현재 점수가 최소 1점 이상이라면, 해당 토큰을 뒷면으로 내려놓아
token[i]만큼 파워를 얻는 대신 1점을 잃습니다.
우리의 목표는 토큰을 원하는 만큼(0개부터 전부까지) 사용한 후 얻을 수 있는 최대 점수를 구하는 것입니다.
예를 들어, 입력이 tokens = [100, 200, 300, 400]이고 P = 200이라면 출력은 2가 됩니다. 파워 200으로 토큰 100을 앞면으로 사용해 1점을 얻고, 남은 파워 100으로 토큰 200을 사용할 수 없으므로 최대 점수는 2점이 되려면 전략적으로 파워를 확보해야 하기 때문입니다.
문제 해결 접근 방법
이 문제는 그리디(Greedy) 알고리즘과 투 포인터(Two Pointer) 기법을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 작은 값의 토큰을 앞면으로 사용해 점수를 모으고,
- 큰 값의 토큰을 뒷면으로 사용해 파워를 회복하는 전략입니다.
단계별 알고리즘
n을 배열v의 크기로,ret을 0으로 초기화합니다.- 배열
v를 오름차순으로 정렬합니다. i = 0(가장 작은 토큰 인덱스),j = n - 1(가장 큰 토큰 인덱스),curr = 0(현재 점수)으로 설정합니다.i <= j이고x >= v[i]인 동안 다음을 반복합니다.i <= j이고x >= v[i]인 동안:x에서v[i]를 차감하고,curr과i를 1씩 증가시킵니다. (앞면으로 사용하여 점수 획득)ret을curr과ret중 최댓값으로 갱신합니다.j >= i이고curr이 0이 아니며x < v[i]인 동안:x에v[j]를 더하고,curr을 1 감소시키며j를 1 감소시킵니다. (뒷면으로 사용하여 파워 회복)
- 최종적으로
ret을 반환합니다.
C++ 구현 예제
아래 코드를 통해 실제 구현 과정을 자세히 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int bagOfTokensScore(vector<int>& v, int x) {
int n = v.size();
int ret = 0;
sort(v.begin(), v.end());
int i = 0;
int j = n - 1;
int curr = 0;
while(i <= j && x >= v[i]){
while(i <= j && x >= v[i]){
x -= v[i];
curr++;
i++;
}
ret = max(curr, ret);
while(j >= i && curr && x < v[i]){
curr--;
x += v[j];
j--;
}
}
return ret;
}
};
main(){
vector<int> v1 = {100,200,300,400};
Solution ob;
cout << (ob.bagOfTokensScore(v1, 200));
}입력
[100,200,300,400] 200
출력
2
동작 원리 설명
위 예제의 실행 흐름을 단계별로 분석하면 다음과 같습니다.
- 배열을 정렬하면
[100, 200, 300, 400]이 됩니다. - 파워 200으로 토큰 100을 앞면으로 사용합니다. 파워는 100이 되고 점수는 1점이 됩니다.
- 파워 100으로는 토큰 200을 사용할 수 없으므로, 가장 큰 토큰 400을 뒷면으로 사용해 파워를 500으로 회복하고 점수는 0점이 됩니다.
- 이제 파워 500으로 토큰 100과 200을 연속해서 앞면으로 사용하면 점수 2점을 얻습니다.
- 따라서 최대 점수인 2가 반환됩니다.
이 알고리즘의 시간 복잡도는 정렬에 의해 지배되므로 O(n log n)이며, 공간 복잡도는 추가 배열 없이 포인터만 사용하므로 O(1)입니다.