1561. Maximum Number of Coins You Can Get

Maximum Number of Coins You Can Get - LeetCode

3의 배 수개의 코인이 들어있는 list가 주어진다.

임의의 코인 3개씩을 집어서 자신은 2번째로 큰 코인만을 가져간다고 할 때, 획득할 수 있는 코인의 최대 합을 반환하는 문제다.

 

1. Greedy

from typing import *
from collections import deque


class Solution:
    def maxCoins(self, piles: List[int]) -> int:
        piles_q = deque(sorted(piles, reverse=True))
        
        answer = 0
        while piles_q:
            alice, me, bob = piles_q.popleft(), piles_q.popleft(), piles_q.pop()
            answer += me

        return answer

해설

1. 임의의 코인 3개를 고를 때 나는 항상 두 번째로 큰 코인만을 가져갈 수 있다.
2. 그렇기 때문에 내가 가져갈 수 있는 최선은 항상 남은 코인들 중 두 번째로 큰 코인이다.
3. 그렇기 때문에 항상 남은 코인에서 가장 큰 코인, 두 번째로 큰 코인을 우선 고른다.
4. 남은 하나의 코인은 남은 코인에서 가장 작은 코인을 고른다. 그렇게 해야 다음번에 내가 고를 코인 후보에서 가장 작은 코인이 제거된다.

내림차순 정렬 후 Queue를 이용해 alice와 me가 가져갈 코인은 왼쪽에서, bob이 가져갈 코인은 오른쪽에서 빼내는 것을 반복하는 것으로 해결할 수 있다.