[프로그래머스] 2024 KAKAO WINTER INTERNSHIP 주사위 고르기 with Kotlin

문제

n개의 주사위가 있다.

이 주사위는 6면으로 되어있고, 각 주사위의 번호는 1~n의 번호를 갖고 있다. (1번 주사위부터 n번 주사위)

 

A가 n/2개의 주사위를 가져가고 B가 나머지 주사위를 가져간다.

각각 가져간 주사위들을 던져 나온 숫자의 합을 비교해 합이 더 큰 사람이 이기는 게임이다.

이때, A가 승리할 확률이 가장 높은 주사위의 조합을 반환하는 문제이다.

 

예시 ( n = 4 )

주사위구성

#1	[1, 2, 3, 4, 5, 6]
#2	[3, 3, 3, 3, 4, 4]
#3	[1, 3, 3, 4, 4, 4]
#4	[1, 1, 4, 4, 5, 5]

 

조합에 따른 결과

A의 주사위	승	무	패
#1, #2	596	196	504
#1, #3	560	176	560
#1, #4	616	184	496
#2, #3	496	184	616
#2, #4	560	176	560
#3, #4	504	196	596

 

1, 4번 주사위를 선택했을 경우 616으로 가장 많은 승을 가져갈 수 있음으로 [1, 4]를 반환한다.

 

풀이과정

1. 나올 수 있는 주사위 조합을 먼저 찾고

2. 해당 조합별 나올 수 있는 주사위의 합을 모두 구한다. (DFS)

3. 주사위의 합을 서로 비교, 이기는 경우와 지는 경우를 탐색 (Binary Search)

  (지는 경우를 탐색하는 이유 - [1,2]번 주사위의 패는 [3,4]번 주사위의 승임으로 조합 절반만 탐색하면 됨)

4. 각 주사위 조합 별로 승이 가장 높은 조합을 반환한다.

 

코드

class Solution {
    val diceSet = mutableListOf<MutableList<Int>>() // 주사위 조합
    val diceSumSetTemp = mutableListOf<Int>() // 주사위들의 합 조합
    
    fun solution(dice: Array<IntArray>): IntArray {
        val n = dice.size / 2
        
        // 주사위 조합
        diceSetFunc(dice.size, n, 0, mutableListOf<Int>())
        
        // 조합에 따른 승패 결과
        val result = IntArray(diceSet.size){0}
        
        for(a in 0 until diceSet.size/2){
            val b = diceSet.size-1-a
            
            val a_Set = mutableListOf<Int>()
            diceSumSet(dice, a, 0, 0) //주사위들의 합 탐색
            a_Set.addAll(diceSumSetTemp)
            a_Set.sort()
            
            val b_Set = mutableListOf<Int>()
            diceSumSet(dice, b, 0, 0)
            b_Set.addAll(diceSumSetTemp)
            b_Set.sort()
            
            // 이분 탐색으로 찾아야됨..
            var win = 0 // a 승
            var lose = 0 // b 승
            for(num in a_Set){
                win += binarySearch(b_Set, num, true)
                lose += binarySearch(b_Set, num, false)
            }
            
            result[a] = win
            result[b] = lose
        }
        
        // 승률 높은 조합 선택
        val maxNumIndex = result.indexOf(result.maxOf{it})
        return diceSet[maxNumIndex].map{ it+1 }.toIntArray()
    }
    
    fun binarySearch(list: MutableList<Int>, target: Int, win: Boolean): Int{
        var start = 0
        var end = list.size-1
        
        while(start <= end){
            val mid = (start + end)/2
            
            if(win){
                if(list[mid] < target){
                    start = mid + 1
                }
                else{
                    end = mid - 1
                }
            }
            else{
                if(list[mid] <= target){
                    start = mid + 1
                }
                else{
                    end = mid - 1
                }
            }
        }
        
        return if(win) end + 1 else list.size - start
    }
    
    // 주사위들의 합 탐색
    fun diceSumSet(dice: Array<IntArray>, index: Int, setIndex: Int, sum: Int){
        if(setIndex >= diceSet[index].size){
            diceSumSetTemp.add(sum)
            return
        }
        
        if(sum == 0) diceSumSetTemp.clear()
        
        val diceIndex = diceSet[index][setIndex]
        for(i in 0 until 6){
            val num = dice[diceIndex][i]
            diceSumSet(dice, index, setIndex+1, sum + num)
        }
    }
    
    // 주사위 조합 탐색
    fun diceSetFunc(size: Int, n: Int, count:Int, temp: MutableList<Int>){
        if(count >= n){
            diceSet.add(temp)
            return
        }
        var start = 0
        if(temp.size != 0) start = temp[temp.size-1]
        
        for(i in start until size){
            if(temp.contains(i)) continue
            val newTemp = mutableListOf<Int>()
            newTemp.addAll(temp)
            newTemp.add(i)
            
            diceSetFunc(size, n, count+1, newTemp)
        }
    }
}