프로그래머스 - 주사위 고르기(JAVA)

문제 링크

---

풀이

처음에는 문제를 읽고 브루트포스를 떠올리고 구현하려던 도중, 최악의 경우 시간초과가 날 수 있다는 사실을 알아챘다.
예를 들어 주사위가 10개인 경우 주사위를 5개 뽑는 경우 수는 10C5 (=252), 각 조합마다 승, 무, 패를 판단하는 경우의 수는 6^10으로 총 연산의 수는 6^10 x 10C5(252)로 약 150억의 연산 횟수가 나오게 된다.
모든 과정을 브루트포스를 이용해 문제를 풀지 않고 다른 방법도 병행하며 수행속도를 어떻게 빠르게 할 수 있을까 생각하던 도중, 각 조합마다 승, 패를 판단하는 경우의 수를 빠르게 구할 수 있는 방법을 떠올려 냈고, 각 조합의 승리 횟수를 기록해 이분탐색을 이용하는 방법을 생각했다.

1. dfs를 이용해 n개의 주사위 중 절반(n/2)만큼의 주사위을 뽑아내는 모든 경우의 수 중 하나를 오름차순으로 하나씩 구한다. 이 때, 나머지 절반의 주사위가 상대방의 주사위가 된다.
2. 경우의 수를 구할 때 마다 한 번 더 dfs를 이용해 가진 주사위를 굴렸을 때 나올 수 있는 모든 합(key)과 그 합이 나오는 횟수(value)를 map으로 저장한다.(상대방의 주사위도 마찬가지)
3. index 참조를 통한 이분탐색을 위해 상대방의 map을 ArrayList로 변경하고 정렬 후 이분 탐색을 활용해 내가 이기는 횟수를 계산한다.
   3-1. 내가 가진 주사위를 굴렸을 때 나올 수 있는 모든 합에 대해 이분 탐색을 진행한다. 그 모든 합 중 하나를 A, 그 합이 나오는 횟수를 B라고 하자.
   3-2. 상대방이 가진 주사위를 굴렸을 때 나올 수 있는 모든 합(C)의 조합들 사이에서 이분 탐색을 진행하여 A를 기준으로 왼쪽에 A보다 작은 C들이 오도록 한다. (내가 이기는 경우를 판별)
   3-3. 해당 C들에 대해 순회하며 상대방이 가진 주사위를 굴렸을 때 C가 나오는 횟수(D) x B 의 합을 구해 변수에 저장한다.
4. 모든 A에 대해 3번 과정을 마쳤다면 내가 이번 주사위 조합의 이기는 총 경우의 수가 가장 크다면 answer를 갱신하고 다시 1번으로 되돌아 가서 주사위를 뽑는다.
5. 1번의 dfs 순회를 마쳤다면 answer를 출력한다.

주의할 점

• 모든 A에 대해 모든 C와 크기 비교를 하여 하나하나 이기는 경우의 수를 기록하는 브루트포스 알고리즘을 사용할 경우 시간초과가 날 우려가 있다. 그렇기에 이분탐색을 이용해 해당 연산의 시간을 단축한 것!
• java의 Map 자료형의 경우 이분 탐색을 하기 위해 필요한 index를 이용한 순회가 불가하다. Iterator를 사용해 Map을 순회하며 ArrayList에 저장해둔다.

 ArrayList<pair> resultListB = new ArrayList<>();

        Iterator<Integer> keys = resultMapB.keySet().iterator();
        while (keys.hasNext()) { // Map 순회
            Integer key = keys.next();
            resultListB.add(new pair(key, resultMapB.get(key)));
        }

• 이분 탐색을 하기 위해 ArrayList 정렬까지 해준다.

// 이분탐색을 위한 배열 정렬 -> Key값 기준 오름차순

        Comparator<pair> cp = new Comparator<pair>() {
            @Override
            public int compare(pair o1, pair o2) {
                return o1.a - o2.a;
            }
        };

        resultListB.sort(cp);

---

코드

import java.util.*;

class Solution {

    int max = 0, tmpMax = 0;
    static int[][] dice;
    Stack<Integer> currentDiceList, answerDiceList = new Stack<Integer>();
    Map<Integer, Integer> resultMap = new HashMap<>();

    public int[] solution(int[][] dice) {

        this.dice = dice;

        selectDice(0, 0, new Stack<Integer>()); // dfs

        int[] answer = new int[answerDiceList.size()];

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

        return answer;
    }

    public void selectDice(int depth, int index, Stack<Integer> diceList) { // 사용할 주사위의 조합 구하기

        if (depth == dice.length/2) {
            // selected

            this.currentDiceList = diceList;


            // 굴려서 나온 각 수의 합을 map으로 저장하기

            resultMap.clear();
            rollDice(0, 0, diceList);
            Map<Integer, Integer> resultMapA = new HashMap<>(resultMap); // 깊은 복사


            // 상대의 주사위도 결정
            Stack<Integer> diceListB = new Stack<Integer>();
            for (int i = 0; i < dice.length; i++) {
                if (!diceList.contains(i)) diceListB.add(i);
            }

            resultMap.clear();
            rollDice(0, 0, diceListB);
            Map<Integer, Integer> resultMapB = new HashMap<>(resultMap);


            calc(resultMapA, resultMapB);// binary search

            return;
        }


        for (int i = index; i < dice.length; i++) {
            diceList.push(i);
            selectDice(depth + 1, i + 1, diceList);
            diceList.pop();
        }
    }

    public void rollDice(int depth, Integer sum, Stack<Integer> diceList) {
        // 굴려서 나온 각 수의 합을 구해서 map으로 저장
        // Key : 각 수의 합, Value : 해당 합이 나오는 총 횟수

        if (depth == dice.length/2) {
            if (resultMap.get(sum) == null)
                resultMap.put(sum, 1);
            else
                // 위의 if문이 없다면 가장 처음의 호출에서 resultMap.get(sum)은 null을 반환하게 되므로 런타임 에러 발생
                resultMap.put(sum, resultMap.get(sum) + 1);

            return;
        }

        for (int i = 0; i < 6; i++) {
            sum += dice[diceList.get(depth)][i];
            rollDice(depth + 1, sum, diceList);
            sum -= dice[diceList.get(depth)][i];
        }
    }

    public void calc(Map<Integer, Integer> resultMapA, Map<Integer, Integer> resultMapB) {

        // 인덱스를 활용한 비교를 위해 map을 lsit<pair<int, int>> 형태로 변환해준다.

        class pair {
            public Integer a, b;

            pair(int a, int b) {
                this.a = a;
                this.b = b;
            }
        }

        ArrayList<pair> resultListB = new ArrayList<>();

        Iterator<Integer> keys = resultMapB.keySet().iterator();
        while (keys.hasNext()) { // Map 순회
            Integer key = keys.next();
            resultListB.add(new pair(key, resultMapB.get(key)));
        }

        // 이분탐색을 위한 배열 정렬 -> Key값 기준 오름차순

        Comparator<pair> cp = new Comparator<pair>() {
            @Override
            public int compare(pair o1, pair o2) {
                return o1.a - o2.a;
            }
        };

        resultListB.sort(cp);

        // 이분 탐색을 활용해 이기는 횟수를 계산한다.

        tmpMax = 0;
        for (int i : resultMapA.keySet()) {

            int left = 0, right = resultListB.size() - 1;
            int mid = (left + right) / 2;


            while (left <= right) {

                mid = (left + right) / 2;

                if (i > resultListB.get(mid).a)
                    left = mid + 1;
                else if (i == resultListB.get(mid).a)
                    break;
                else
                    right = mid - 1;

            }

            for (int j = 0; j < mid; j++) {
                tmpMax += resultListB.get(j).b * resultMapA.get(i);
            }
            if(i > resultListB.get(mid).a) tmpMax += resultListB.get(mid).b * resultMapA.get(i);

        }
        if (max < tmpMax) {
            max = tmpMax;
            answerDiceList.clear();
            for (int j : currentDiceList)
                answerDiceList.push(j);
        }

    }


}

---

결론

구현만 하면 되는 생각보다 간단한 문제라고 생각했는데, 시간복잡도도 고려해야 하고 조합과 이분탐색을 이용해야 했기에 쉽지 않은 문제였던 것 같다.