[Leetcode][948] Bag of Tokens

문제 : https://leetcode.com/problems/bag-of-tokens/

---

tokens 배열을 오름차순 정렬한다.

tokens 배열의 앞에서부터 토큰을 power로 얻으면서 탐색해나간다. (앞으로 탐색중인 인덱스는 i, 토큰 배열 요소 값은 tokens[i]라 하자.)

만약 탐색중에 남은 power로 tokens[i]를 얻을 수 없다면 토큰을 하나 돌려주고 가장 비싼 토큰(인덱스 r이라 하자. r의 초기값은 tokens 배열의 마지막 인덱스와 같다.)의 power부터 가져온다. (낮은 power로 큰 power를 얻은 것과 같다.)

power를 가져온 뒤는 반드시 tokens[i]를 얻을 수 있다. 왜냐하면 인덱스는 i < r인데 오름차순 정렬했기 때문에 tokens[i] <= tokens[r] 이다. 즉 power를 가져온다는 뜻은 tokens[r] 만큼 power를 가져온다면 tokens[i]를 반드시 얻을 수 있다.

탐색중에 남은 power로 tokens[i]를 얻을 수 없고 토큰도 하나도 없다면 더 이상 얻을 수 있는 토큰이 없으므로 탐색을 종료한다.

tokens[r]을 가져오는 것은 tokens[r]도 탐색을 했다는 뜻이므로 r보다 같거나 큰 범위는 탐색 범위에서 제외시켜준다. 

탐색 중 얻을 수 있는 point 들 중 최대값일 때가 정답이 된다.

그리디 방법이다.

시간복잡도는 정렬하는데 가장 오래걸리므로 tokens 배열 크기를 N이라 하면 O(NlogN).

---

소스코드 : https://gist.github.com/fpdjsns/a18db75dcd55975f300da7664f947177