[프로그래머스] Swift - n + 1 카드게임

https://school.programmers.co.kr/learn/courses/30/lessons/258707

프로그래머스

 

2024.01.31 기준 Level 3

 

알고리즘 공부를 위해 풀고 기록하는 글입니다!
참고만 해주시고 더 좋은 풀이법이 있다면 알려주세요!

 

아이디어

[문제 조건]

• 1~n 사이의 수가 적힌 카드 배열 (cards)와 동전 개수 coin이 주어진다. (n은 6의 배수)
• 처음에 cards 배열에서 n/3 장을 뽑아 모두 가진다. 
• 1라운드 부터 게임이 시작되며 각 라운드 시작마다 2장을 새로 뽑는다.
• cards 배열에 남은 카드가 없다면 게임 종료
• 뽑은 카드는 카드 한 장당 동전 1개를 소모하여 가지거나 동전을 소모하지 않고 버릴 수 있다.
• 카드에 적힌 수의 합이 n+1이 되도록 카드 두장을 내고 다음 라운드 진출이 가능하다.
• 만약 n+1이 되도록 카드를 낼 수 없다면 게임을 종료한다.
• 게임에서 도달 가능한 최대 라운드 수를 리턴하자!

 

우선 게임의 종료 조건은 총 2개 입니다.

1. cards 배열에서 더 이상 뽑을 카드가 없는 경우

2. 내가 가진 카드 중에서 n+1을 만들 수 있는 카드 조합이 없는 경우

 

 

결국 우리는 동전을 써서 새 카드를 가질지 말지를 선택해야 하는 경우의 수가 나누어지고 이 경우의 수들을 탐색해서 가장 라운드를 높게 진출 할 수 있는 케이스를 찾아야 합니다.

 

가장 쉽게 생각할 수 있는 아이디어는 dfs 또는 bfs를 사용해서 각 라운드마다 가능한 경우의 수를 모두 탐색하는 것입니다.

 

1. 코인 2개 써서 새로 뽑은 2장 모두 가지고 원래 내 카드 모음과 합쳐서 n+1이 되는 모든 케이스들을 구해서 탐색

2. 코인 1개 써서 새로 뽑은 카드 중 첫 번째 카드를 가지고 원래 내 카드 모음과 합쳐서 n+1이 되는 모든 케이스들을 구해서 탐색

2. 코인 1개 써서 새로 뽑은 카드 중 두 번째 카드를 가지고 원래 내 카드 모음과 합쳐서 n+1이 되는 모든 케이스들을 구해서 탐색

3. 코인 0개 써서 새로 뽑은 카드 중 0장을 가지고 원래 내 카드 모음과 합쳐서 n+1이 되는 모든 케이스들을 구해서 탐색

 

하지만 이렇게 구현하면 너무 많은 케이스들이 생기고 특히 코인 1개를 사용한 경우에는 둘 중에 어떤 카드를 고를지에 대한 경우의 수도 추가로 생기게 됩니다.

 

 

그래서!

이 문제에서 필요한 아이디어는 미리 코인을 사용해서 가질 카드를 정하지 말고 필요한 순간에 코인을 소비해서 필요한 카드를 가져오는 방식을 사용하는 것이었습니다.

 

즉, 게임의 진행 방식에서는 당연히 현재 라운드에서 즉시 카드 2장을 뽑고 코인을 쓸지 말지 정해야 하지만 문제를 푸는 입장에서는 전지적인 관점에서 가장 라운드를 높게 진출시킬 수 있는 경우의 수만 찾으면 됩니다.

 

따라서, 실제로 내가 가진 카드 집합(cur)과 현재 라운드까지 뽑은 카드 중에서 아직 가져오지 않은 카드를 담은 집합(draw)을 분리하여 저장합니다. 다음 라운드에 진출하면 draw에 새로 뽑은 2개의 카드를 넣으면 됩니다. (아직 이 카드들은 코인을 소비해서 가져오는 것을 정하지 않은 예비 카드군에 해당됩니다.)

 

 

각 라운드에서 경우의 수는 다음과 같이 3가지로 정해집니다.

 

1. 실제로 내가 가진 카드 집합인 cur에서 n+1을 만들 수 있다면 그 카드 2장을 내고 다음 라운드에 바로 진출하면 됩니다.
2. cur에서 n+1을 만들 수 없다면 cur에서 1장, draw에서 1장을 가져와서 n+1을 만들어서 내고 다음 라운드에 진출하면 됩니다.
3. cur에서 1장, draw에서 1장씩 뽑아서는 n+1을 만들 수 없다면 draw에서 2장을 뽑아서 n+1을 만들어서 내고 다음 라운드에 진출하면 됩낟.

위 3가지 방법이 모두 불가능 하다면 현재 라운드가 도달 가능한 최대 라운드가 됩니다.

 

 

 

 

풀이

1. removeTwoCards 함수 구현

// 합이 n+1인 카드 2장 내기
fileprivate func removeTwoCards(cards: Set<Int>, n: Int) -> Set<Int> {
  var cards = cards
  
  for num in cards {
    let target = n+1 - num
    
    if cards.contains(target) {
      cards.remove(num)
      cards.remove(target)
      
      return cards
    }
  }
  
  return cards
}

 

카드 집합에서 n+1을 만들 수 있는 2개의 카드를 소모하고 남은 카드 집합을 리턴하는 함수입니다.

2. removeOneCards 함수 구현

// 합이 n+1인 카드 2장 내기
fileprivate func removeOneCards(cards: Set<Int>, drawCards: Set<Int>, n: Int) -> (newCards: Set<Int>, newDrawCards: Set<Int>) {
  var cards = cards
  var drawCards = drawCards
  
  for num in cards {
    let target = n+1 - num
    
    if drawCards.contains(target) {
      cards.remove(num)
      drawCards.remove(target)
      
      return (cards, drawCards)
    }
  }
  
  return (cards, drawCards)
}

 

두 개의 서로 다른 카드 집합을 받아서 각각의 집합에서 합이 n+1을 만드는 1개씩 카드를 소모하고 남은 카드들의 집합을 리턴하는 함수입니다.

 

3. solution 함수 구현

fileprivate func solution(_ coin:Int, _ cards:[Int]) -> Int {
  let n = cards.count
  
  var result = 0
  
  func dfs(cur: Set<Int>, draw: Set<Int>, round: Int, coin: Int) {
    let cardsIndex = n / 3 + round * 2 - 2
    
    result = max(result, round)
    
    if cardsIndex == n {
      return
    }
    
    let newCards = cards[cardsIndex...cardsIndex+1] // 2장 뽑기
    let newDraw = draw.union(newCards)
    
    // 현재 가지고 있는 카드 모음에서 n+1 만들어서 내기
    let cardsAfterUsing0coin = removeTwoCards(cards: cur, n: n)
    
    if cardsAfterUsing0coin.count != cur.count {
      dfs(cur: cardsAfterUsing0coin, draw: newDraw, round: round+1, coin: coin)
      return
    }
    
    if coin >= 1 {
      // coin 1개 써서 지금까지 뽑은 카드 중에서 1개를 가져와서 사용
      let cardsAfterUsing1coin = removeOneCards(cards: cur, drawCards: newDraw, n: n)
      
      if cardsAfterUsing1coin.newCards.count != cur.count {
        dfs(cur: cardsAfterUsing1coin.newCards, draw: cardsAfterUsing1coin.newDrawCards, round: round+1, coin: coin-1)
        return
      }
    }

    if coin >= 2 {
      // coin 2개 써서 지금까지 뽑은 카드 중에서 2개를 가져와서 사용
      let cardsAfterUsing2coin = removeTwoCards(cards: newDraw, n: n)
      
      if cardsAfterUsing2coin.count != newDraw.count {
        dfs(cur: cur, draw: cardsAfterUsing2coin, round: round+1, coin: coin-2)
        return
      }
    }
  }
  
  let startCardsIndex = n/3
  let cur = cards[0..<startCardsIndex]
  dfs(cur: Set(cur), draw: [], round: 1, coin: coin)
  
  return result
}

 

dfs로 탐색을 수행합니다.

 

cur은 현재 실제로 가진 카드들을 담고 있고 draw는 현재 라운드까지 뽑고 아직 코인을 사용하지 않은 카드들을 담게 됩니다.

 

앞서 설명드린 3개의 경우의 수를 순서대로 탐색합니다.

만약 cur의 카드들만으로도 n+1을 만들 수 있다면 그 카드 2장을 내고 다음 라운드로 진출시킨 뒤 return합니다.

 

coin을 1개 쓰는 경우에는 cur과 draw에서 한 장씩 소모하고 coin을 1 감소시킨 뒤 다음 라운드 진출 시킨 뒤 return합니다.

 

coin을 2개 써야 하는 경우에서는 draw 집합에서 두 장을 소모하고 coin을 2 감소시킨 뒤 다음 라운드로 진출시킵니다.

 

 

 

마무리

필요한 알고리즘 지식은 dfs로 충분했지만, 너무 게임의 진행 방식에만 매몰되어 매 라운드마다 뽑은 2장의 카드에서만 코인을 지불하고 어떤 카드를 선택할지를 고르게 된다면 풀이가 복잡해지는 문제였습니다.

 

게임의 특성과 우리가 구하고자 하는 값의 특성을 고려하여 과거의 라운드에서 소비할 코인을 필요한 시기에 늦게 결정한다는 아이디어가 중요했습니다.