[프로그래머스] 주사위 고르기 (Swift)

https://school.programmers.co.kr/learn/courses/30/lessons/258709?language=swift

프로그래머스

 

 

A와 B라는 친구들이 있습니다. 그들의 앞에는 N개의 주사위가 있고요. 이걸 딱 반띵해서 가져갈겁니다.

주사위는 평범하게 정육면체인데, 그 안에 적혀 있는 숫자는 1~100으로 랜덤입니다. 중복도 있구요.

자, A와 B는 본인들이 가져간 주사위를 한번씩 다 굴려서 나온 값을 더할거에요. 그 값으로 누가 더 큰 수가 나왔나~ 겨루는 겁니다.

이때, A가 이길 확률이 가장 높게 하려면, 어떤 주사위를 골라 가져가야 하는지 구하는 문제입니다. ^_^

 

1. A와 B가 가져가는 주사위의 조합을 구합니다. (ex. A: 1,2번째 주사위 가져감, B: 3,4번째 주사위 가져감 -> 이걸 모든 경우를 구함)

 

2. 한 사람이 가져갈 수 있는 주사위 조합 마다, 나올 수 있는 숫자들을 합한 값 : 그 값이 나오는 횟수 를 딕셔너리로 저장합니다.

 

3. 이제 다시 1.의 결과를 사용해서, 각자 주사위를 가져가는 경우를 한 게임이라고 할 때, 그 게임에서 A가 이기는 횟수가 가장 많은 주사위 조합을 구해서 정렬해서 변환합니다. (저는 dice 탐색하기 편하라고 0번째부터 사용해서 1을 더해주는 과정도 추가됐습니다.)

 

소스코드

import Foundation

var diceSets:[[Int]] = []

func dfs(_ n:Int, _ i:Int, _ diceSet:[Int]) {
    if diceSet.count == n/2 {
        diceSets.append(diceSet)
        return
    }
    
    if i == n { return }
    
    dfs(n, i+1, diceSet+[i])
    dfs(n, i+1, diceSet)
} 

func getDiceSets(_ n: Int) -> [([Int], [Int])] {
    dfs(n, 0, [])
    let ABSets:[([Int], [Int])] = diceSets.map { ASet in 
                                                let BSet = Set(Array(0..<n)).subtracting(Set(ASet))
                                                return (ASet, Array(BSet).sorted())
                                               }
    return ABSets
}

func solution(_ dice:[[Int]]) -> [Int] {
    
    // 1. A와 B가 가질 수 있는 주사위 조합 구하기
    let n: Int = dice.count
    let ABDiceSet: [([Int], [Int])] = getDiceSets(n)
    
    // 2. 각 조합의 접수합 : 횟수 구하기
    var sumCntMap:[[Int]:[Int:Int]] = [:] // [[Int] 조합 : [점수합:횟수]]
    for diceSet in diceSets {
        //ex. diceSet = [0,1]
        var sumCnt:[Int:Int] = [:]
        
        func getSumOf(_ com:[Int], _ sum:Int, _ diceidx:Int) {
            if diceidx == com.count {
                sumCnt[sum, default:0] += 1
                return
            }
            
            for i in 0..<6 {
                getSumOf(com, sum+dice[com[diceidx]][i], diceidx+1)
            }
        }
        
        getSumOf(diceSet, 0, 0)
        sumCntMap[diceSet] = sumCnt
    }
    
    // 3. A가 몇번 이기는지 계산
    var maxWinSet:[Int] = []
    var maxWinCnt = 0
    for (A, B) in ABDiceSet {
        // A: A가 가져간 주사위 조합
        // A가 가져간 주사위 조합 - 가능 점수합 : 횟수
        // B도 동일
        var AScores = sumCntMap[A] // 가능 점수합:횟수
        var BScores = sumCntMap[B]
        
        var winCnt = 0
        
        for (ascore, acnt) in AScores! {
            for (bscore, bcnt) in BScores! {
                if ascore > bscore {
                    winCnt += acnt*bcnt
                }
            }
        }
        if maxWinCnt < winCnt {
            maxWinCnt = winCnt
            maxWinSet = A
        }
    }
        
    return maxWinSet.map{ $0 + 1 }.sorted()
}