[코딩테스트] ♠️ 카드 게임 - kakao 2024 winter

문제링크

난이도

레벨 3

유형

구현, DFS, 그리디?

소요시간

2시간 + 카카오 문제 해설

회고

처음에는 DFS로 경우의 수를 계산하려고 했는데 실패함. 질문 게시판을 보고 풀어봤지만 구현 실패. 카카오 해설집 보고 풀이함

일단 카드를 챙겨두고, 다음 라운드에서 카드가 필요한 경우 돈을 내는 방식을 생각해내는게 힘들었다.

코드

func solution(_ coin:Int, _ cards:[Int]) -> Int {
    let n = cards.count

    var head = n / 3
    var coins = coin
    var deck = Set<Int>()
    var keep = Set<Int>()

    (0..<head).forEach { deck.insert(cards[$0]) }

    var round = 1

    func none() -> Bool {
        let copy = deck
        for card in copy {
            let target = n + 1 - card
            if (1...n) ~= target && deck.contains(target) {
                deck.remove(card)
                deck.remove(target)
                return true
            }
        }
        return false
    }

    func oneCoin() -> Bool {
        guard coins >= 1 else { return false }

        for card in deck {
            let target = n + 1 - card
            if (1...n) ~= target && keep.contains(target) {
                keep.remove(target)
                deck.remove(card)
                coins -= 1
                return true
            }
        }
        return false
    }

    func twoCoin() -> Bool {
        guard coins >= 2 else { return false }

        for card in keep {
            let target = n + 1 - card
            if (1...n) ~= target && keep.contains(target) {
                keep.remove(target)
                keep.remove(card)
                coins -= 2
                return true
            }
        }
        return false
    }

    while true {
        if head + 1 >= n { break }
        keep.insert(cards[head])
        keep.insert(cards[head+1])
        head += 2

        if none() || oneCoin() || twoCoin() {
            round += 1
            continue
        }
        break
    }

    return round
}