[2024] 3/4 Leetcode Daily Challenge 948. Bag of Tokens

948. Bag of Tokens

코드

풀이

• face-up

if power >= tokens[l]:
	power -= tokens[l]
	l += 1
	curScore += 1
	res = max(res, curScore)

• face-down

elif curScore > 0:
	power += tokens[r] # greedy algorithm
    r -= 1
    curScore -= 1

greedy algorithm(그리디 알고리즘) 이용:

tokens.sort()

다음과 같이 토큰 리스트를 오름차순으로 정렬하였기 때문에,
power += tokens[r] 을 해주면 현재 토큰 리스트 중에 가장 큰 토큰 값 부터 가져오게 된다.

• 예외 처리

else:
	break

점수가 0점이어서 power를 가져올 수 없거나, power가 token보다 작을 경우
face-up/face-down 둘 다 할 수 없으므로 루프를 종료한다.
break를 사용하면 while문을 탈출한 뒤 최종 점수를 return 하게 된다.

알고리즘

• 그리디(Greedy)
  탐욕 알고리즘이라고도 하며, 최적해를 구하는 데에 사용되는 근사적인 방법으로 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식
  참고 영상

• 게임 이론(game theory)

시간 복잡도

O(nlogn)