[2024 KAKAO INTERN] 주사위 고르기

 

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

프로그래머스

 

문제 유형

• DP + 누적합
• DFS + 이분 탐색

 

문제 난이도

• Lev3

 

문제 분석

A와 B가 주사위를 N / 2 개씩 나눠갖고, 각 주사위를 모두 돌려, 나온 숫자의 합을 서로 비교해서 A가 승리할 수 있도록 가장 승률이 좋은 주사위 번호들을 출력하는 문제이다.

문제를 이해하는덴 어렵지 않았지만, 시간 초과를 해결하기 위해 고민하다 다른 사람들의 풀이를 참고한 문제이다.

우선 문제에서 핵심은
1. (N / 2)개의 주사위 고르기
2. 고른 주사위와 고르지 않은 주사위들간의 나올 수 있는 모든 합의 경우의 수를 비교해서 승리할 확률이 높은 주사위를 갱신하기

우선 1번은 n이 최대 10개라고 했을 때, 10C5 = 252개이므로, 시간 초과가 나지 않기 때문에 조합을 사용하였다.

2번은 선택한 주사위와 선택하지 않은 주사위를 각각, 합을 계산하기 위해 DFS를 활용해서 합들을 배열에 저장해주었다.
이렇게 되면 각각 6^5 = 7776가지인데, 이걸 단순하게 완전 탐색을 하게 되면 6^10 = 7776 * 7776 이고, 조합까지 곱하게 되면252 * 7776 * 7776 이므로 시간 초과가 날 것이다.

따라서 시간 복잡도를 줄이기 위해 선택하지 않은 주사위들을 정렬한 이후, 이분 탐색을 통해 개수들을 더해주었다. 
-> 사실 현재 부분도 시간 초과가 날 수 있지만, 프로그래머스의 JVM 성능 및 최적화 수행 등으로 문제에서는 시간 초과가 나지 않았지만, 빠르게 풀려면 DP + 누적합을 사용해야 한다.

 

 

코드 분석

 

조합을 통해 주사위를 선택하는 코드이다.

(N / 2) 개를 선택하면, 주사위들간의 합을 비교하고, 가장 승률이 좋은 주사위로 갱신한다.

현재 선택된 주사위 번호는 배열의 인덱스에 해당하므로 +1 해준다.

// 주사위 선택
static void pickDice(int cnt, int start, int[][] dice) {

    if(cnt == N / 2) {

        int winCount = calculateWin(dice);

        if(max < winCount) {
            max = winCount;

            for(int i = 0; i < selected.size(); i++) {
                result[i] = selected.get(i) + 1;
            }
        }

        return;
    }

    for(int i = start; i < N; i++) {

        selected.add(i);
        pickDice(cnt+1, i+1, dice);
        selected.remove(selected.size()-1);
    }

}

 

주사위들간의 합을 계산하는 코드이다. 우선 비교할 주사위를 정렬하고, 이분 탐색을 통해, A의 주사위 합을 target으로 더 작다면 작은 개수 만큼은 이기는 경우이므로, 카운팅 해준다.

static int calculateWin(int[][] dice) {
        
    int count = 0;

    makeArrAB(dice);

    // arrA, arrB에 대하여 승패를 결정한다.

    Collections.sort(arrB);

    // 승부를 결정할 때, 이분 탐색을 통하여 시간복잡도를 줄인다. O(6^5 * log 6^5)

    for(int i = 0; i < arrA.size(); i++) {

        int target = arrA.get(i);

        int st = 0;
        int et = arrB.size() - 1;

        int idx = -1;
        while(st <= et) {

            int mid = (st + et) >> 1;

            if(target <= arrB.get(mid)) {
                et = mid - 1;
            } else {
                idx = Math.max(idx, mid);
                st = mid + 1;
            }

        }
        if(idx != -1) count += idx + 1;

    }

    return count;
}

 

주사위들의 합을 저장하기 위해 사용하는 코드이다. 깊이 우선 탐색을 통해, 모든 경우의 합을 저장한다.

// 선택된 주사위들의 합 분포를 저장
static void sumDice(int cnt, int sum, int[][] dice, List<Integer> arr) {

    if(cnt == N / 2) {
        arr.add(sum);
        return;
    }

    for(int i = 0; i < 6; i++) {
        int newSum = sum + dice[cnt][i];
        sumDice(cnt+1, newSum, dice, arr);
    }   
}

 

선택된 주사위들이 갖는 주사위 면 번호를 저장하고, A, B 주사위에 대해 합 분포를 저장하기 위해 sumDice()를 호출한다.

static void makeArrAB(int[][] dice) {
        
    // 선택된 주사위들의 합 분포를 저장한 배열
    arrA = new ArrayList<>();
    arrB = new ArrayList<>();

    int[][] diceA = new int[N / 2][6];
    int[][] diceB = new int[N / 2][6];

    int a = 0, b = 0;
    for(int i = 0; i < N; i++) {

        if(selected.contains(i)) {
            diceA[a++] = dice[i];
        } else {
            diceB[b++] = dice[i];
        }

    }

    sumDice(0, 0, diceA, arrA);
    sumDice(0, 0, diceB, arrB);

}

 

전체 코드

import java.io.*;
import java.util.*;

class Solution {
    
    // 주사위 선택
    static void pickDice(int cnt, int start, int[][] dice) {
        
        if(cnt == N / 2) {
            
            int winCount = calculateWin(dice);
            
            if(max < winCount) {
                max = winCount;
                
                for(int i = 0; i < selected.size(); i++) {
                    result[i] = selected.get(i) + 1;
                }
            }
            
            return;
        }
        
        for(int i = start; i < N; i++) {
            
            selected.add(i);
            pickDice(cnt+1, i+1, dice);
            selected.remove(selected.size()-1);
        }
        
    }
    
    static int calculateWin(int[][] dice) {
        
        int count = 0;
        
        makeArrAB(dice);
        
        // arrA, arrB에 대하여 승패를 결정한다.
        
        Collections.sort(arrB);
        
        // 승부를 결정할 때, 이분 탐색을 통하여 시간복잡도를 줄인다. O(6^5 * log 6^5)
        
        for(int i = 0; i < arrA.size(); i++) {
            
            int target = arrA.get(i);
            
            int st = 0;
            int et = arrB.size() - 1;
            
            int idx = -1;
            while(st <= et) {
                
                int mid = (st + et) >> 1;
                
                if(target <= arrB.get(mid)) {
                    et = mid - 1;
                } else {
                    idx = Math.max(idx, mid);
                    st = mid + 1;
                }
                
            }
            if(idx != -1) count += idx + 1;
            
        }
        
        return count;
    }
    
    
    // 선택된 주사위들의 합 분포를 저장
    static void sumDice(int cnt, int sum, int[][] dice, List<Integer> arr) {
        
        if(cnt == N / 2) {
            arr.add(sum);
            return;
        }
        
        for(int i = 0; i < 6; i++) {
            int newSum = sum + dice[cnt][i];
            sumDice(cnt+1, newSum, dice, arr);
        }   
    }
    
    static void makeArrAB(int[][] dice) {
        
        // 선택된 주사위들의 합 분포를 저장한 배열
        arrA = new ArrayList<>();
        arrB = new ArrayList<>();
        
        int[][] diceA = new int[N / 2][6];
        int[][] diceB = new int[N / 2][6];
        
        int a = 0, b = 0;
        for(int i = 0; i < N; i++) {
            
            if(selected.contains(i)) {
                diceA[a++] = dice[i];
            } else {
                diceB[b++] = dice[i];
            }
            
        }
        
        sumDice(0, 0, diceA, arrA);
        sumDice(0, 0, diceB, arrB);
        
    }
    
    
    
    static int N, max = 0;
    static int[] result;
    static List<Integer> selected, arrA, arrB;
    public int[] solution(int[][] dice) {
        N = dice.length;
        result = new int[N / 2];
        
        selected = new ArrayList<>();
        
        pickDice(0, 0, dice);
        
        
        return result;
        
    }
}