[프로그래머스 258707] 카카오 겨울 인턴십, n + 1 카드게임, swift

문제 설명

난이도: level3

문제 풀이

이 문제의 핵심은 카드를 라운드마다 뽑을 생각을 하지 않고 킵 해두는 것이다.

 

keepCards라는 배열을 만들고 라운드마다 카드 2장을 킵해둔다.

내가 가지고 있는 카드는 myCards라는 배열에 저장한다.

 

1.  myCards에서 타겟 넘버를 만든다. (코인 0개 소모)

2. 1번이 안되면 코인 1개 이상 있을 때, myCards에서 1장 + keepCards에서 1장 써서 타겟 넘버를 만든다. (코인 1개 소모)

3. 2번이 안되면 코인 2개 이상 있을 때, keepCards에서 2장을 써서 타겟 넘버를 만든다. (코인 2개 소모)

 

만약 1,2,3에서 타겟 넘버를 못찾는다면 라운드 종료

코인도 없고 남아있는 카드도 없다면 종료

 

예제로 설명하자면

 

코인 = 4개, 카드 순서는 [3, 6, 7, 2, 1, 10, 5, 9, 8, 12, 11, 4]가 있다.

 

<1라운드>

myCards = [3, 6, 7, 2]

keepCards = [1, 10] (1, 10 새 카드 들어옴)

코인 = 4개

 

myCards에서 2장 뽑기 -> 6+7=13, 코인 소모 0개

 

<2라운드>

myCards = [3, 2]

keepCards = [1, 10, 5, 9] (5, 9 새 카드 들어옴)

코인 = 4개

 

myCards에서 2장 뽑기 -> 타겟넘버 만들 수x

myCards에서 1장, keepCards에서 1장 뽑기 -> 3+10=13, 코인 소모 1개

 

 

<3라운드>

myCards = [2]

keepCards = [1, 5, 9, 8, 12] (8, 12 새 카드 들어옴)

코인 = 3개

 

myCards에서 2장 뽑기 -> 타겟넘버 만들 수x

myCards에서 1장, keepCards에서 1장 -> 타겟넘버 만들 수x

keepCards에서 2장 뽑기 -> 1+12 = 13, 코인 소모 2개

 

 

<4라운드>

myCards = [2]

keepCards = [5, 9, 8, 11, 4] (11, 4 새 카드 들어옴)

코인 = 1개

 

myCards에서 2장 뽑기 -> 타겟넘버 만들 수x

myCards에서 1장, keepCards에서 1장 -> 2+11 = 13, 코인 소모 1개

 

 

<5라운드>

myCards = []

keepCards = [5, 9, 8, 4]

코인 = 0개

 

코인도 없고, 내 카드도 없음 -> 라운드 종료

 

 

코드

func solution(_ coin:Int, _ cards:[Int]) -> Int {
    var coin = coin
    let n = cards.count
    var point = n/3
    var myCards = cards[0..<n/3].map {Int(String($0))!} // n/3개 가지고 시작
    var keepCards: [Int] = []
    var round = 1
    let target = n+1
    
myLoop:
    while true {
        // 코인도 없고 낼 수 있는 카드도 없으면
        if (myCards.isEmpty && coin <= 1) || (point == n) {
            break
        }
        let card1 = cards[point]
        let card2 = cards[point+1]
        keepCards.append(card1)
        keepCards.append(card2)

        for i in 0..<myCards.count-1 {
            for j in i+1..<myCards.count {
                let myCard1 = myCards[i]
                let myCard2 = myCards[j]
                // 내 카드에서 2장을 뽑을 수 있으면
                if (myCard1+myCard2) == target {
                    round += 1
                    point += 2
                    myCards = myCards.filter {$0 != myCard1 && $0 != myCard2}
                    continue myLoop
                }
            }
        }
       
        // 코인이 1개 이상 남아있고 내카드+킵해둔 카드를 낼 수 있으면
        if coin >= 1 {
            for i in 0..<myCards.count {
                for j in 0..<keepCards.count {
                    let myCard = myCards[i]
                    let keepCard = keepCards[j]
                    
                    // 내카드 + 킵카드써서 코인 1개 소모
                    if myCard+keepCard == target {
                        round += 1
                        coin -= 1
                        point += 2
                        myCards.remove(at: i)
                        keepCards.remove(at: j)
                        continue myLoop
                    }
                }
            }
        }
        
        // 코인이 2개이상 남아있고 킵해둔 카드에서 다 낼 수 있으면
        if coin >= 2 {
            for i in 0..<keepCards.count-1 {
                for j in i+1..<keepCards.count {
                    let keepCard1 = keepCards[i]
                    let keepCard2 = keepCards[j]
                    
                    // 킵카드 2개 써서 코인 2개 소모
                    if (keepCard1+keepCard2) == target {
                        round += 1
                        coin -= 2
                        point += 2
                        keepCards = keepCards.filter {$0 != keepCard1 && $0 != keepCard2}
                        continue myLoop
                    }
                }
            }
        }
        break
    }
    return round
}

 

 

후기

실제로 카카오 겨울 인터십 코테를 봤었는데 그 당시 이 문제를 풀지 못했다. (아이디어가 안떠올라 손도 안댔던 기억이..ㅋㅋ)

다시 풀 때, 힌트를 조금 보니 '카드를 킵해둔다.' 를 생각해내면 금방 푸는 문제였다. 

계속 그때 그때 최적의 카드를 어떻게 뽑지..? 라는거에 빠져서 생각도 못했다.

아마 힌트를 안봤으면 평생 못풀지 않았을까..ㅎㅎ 어렵다~