[Kotlin] LeetCode 1561 : Maximum Number of Coins You Can Get

Maximum Number of Coins You Can Get - LeetCode

3N개의 코인이 주어집니다. 그리고 3개를 선택하여 2번째로 큰 값을 자신이 가져가고 가장 큰 값을 앨리스가, 가장 작은 값은 밥이 가져갑니다. 이때 나의 최대 값을 구하라고 합니다.

그리디하게 생각을 해봅시다. 결국 총합을 최대한 크게 만들기 위해서는 큰 숫자들을 뽑으면 되겠죠. 하지만 앨리스가 있기에 2번째로 큰 값들을 계속 가져가면 됩니다. 반대로 밥은 가장 작은 코인을 계속 주면 되겠죠. 내가 작은 코인을 가져가는 경우의 수를 제거하면 됩니다.

이제 투포인터 알고리즘을 떠올릴 수 있습니다.
배열을 정렬하고 왼쪽부터 밥에게 주고, 오른쪽부터 앨리스에게 먼저 코인을 준다음 가장 오른쪽에 있는 값을 내가 가져가면 됩니다. 시간복잡도는 O(N)이 소요됩니다. 

class Solution {
    fun maxCoins(piles: IntArray): Int {
        var answer : Int = 0
        var left : Int = 0
        var right : Int = piles.size-1
        piles.sort()
        while (left <= right) {
            right--
            answer += piles[right--]
            left++
        }
        return answer
    }
}