[2024 KAKAO WINTER INTERNSHIP] 주사위 고르기

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

프로그래머스

 

단순한 문제 같았지만 어려웠던 문제이다. 대략적인 아이디어는 다음과 같다.

• A가 가져갈 주사위의 조합을 만든다.
• 각 조합에 대해, A가 자신의 주사위들을 던졌을 때 나올 수 있는 결과 리스트와 B가 자신의 주사위들을 던졌을 때 나올 수 있는 결과 리스트를 구한다.
• 그리고 A의 결과 리스트와 B의 결과 리스트를 비교해서, A가 이기는 횟수가 가장 많은 조합이 정답이다.

위와 같이 계산하면 시간 복잡도는 다음과 같다.

• A가 n개의 주사위 중 절반을 고르는 경우 (10C5)
• A의 주사위에 대한 결과 리스트 생성 (6^5)
  B의 주사위에 대한 결과 리스트 생성 (6^5)
  A와 B의 결과 비교 (6^5 * 6^5)
• ➡️ 10C5 * 6^5 * 6^5 = 약 152억

약 152억으로 시간 초과가 날 것이다. 따라서 시간을 줄여야 하는데, A의 6^5개의 결과와 B의 6^5개의 결과를 비교할 때 완전탐색을 실행하면 6^5 * 6^5이지만, 이분탐색을 실행하면 6^5 * log6^5이다. 즉, 이분 탐색을 사용하면 시간 복잡도는 다음과 같다.

• A가 n개의 주사위 중 절반을 고르는 경우 (10C5)
• A의 주사위에 대한 결과 리스트 생성 (6^5)
  B의 주사위에 대한 결과 리스트 생성 (6^5)
  A와 B의 결과 비교 (6^5 * log6*5)
• ➡️ 10C5 * 6^5 * log6^5 = 약 710만

즉, 이분 탐색을 사용하면 된다.

 

정리하면 다음과 같다.

• A가 가져갈 주사위의 조합을 만든다.
• 각 조합에 대해, A가 자신의 주사위들을 던졌을 때 나올 수 있는 결과 리스트와 B가 자신의 주사위들을 던졌을 때 나올 수 있는 결과 리스트를 구한다.
• 그리고 A의 결과 리스트와 B의 결과 리스트를 이분 탐색으로 비교해서, A가 이기는 횟수가 가장 많은 조합이 정답이다.

위 아이디어대로 구현만 하면 된다. 특히 나는 A가 가져간 여러 주사위들을 통해 결과를 계산하는 부분을 구현하지 못했는데, 재귀를 사용하면 된다..! 전체 코드를 참고하자.

import java.util.*;

class Solution {

    int[][] dice;
    int n;
    List<List<Integer>> combination = new ArrayList<>(); // A가 가져갈 주사위 조합 (인덱스)
    int answerWinCnt = 0;
    List<Integer> answerDiceCombination;

    public int[] solution(int[][] dice) {
        this.dice = dice;
        this.n = dice.length;

        // 1. A가 가져갈 주사위 조합 생성
        combine(0, 0, new ArrayList<>());

        // 2. 각 조합에 대해 A의 결과 리스트, B의 결과 리스트 생성 -> 리스트 간 비교
        for (List<Integer> listA : combination) {
            // 2-1. A 결과 리스트 생성
            List<Integer> resultListA = new ArrayList<>();
            getResult(listA, 0, 0, resultListA);

            // 2-2. B 결과 리스트 생성
            List<Integer> listB = calculateListB(listA);
            List<Integer> resultListB = new ArrayList<>();
            getResult(listB, 0, 0, resultListB);

            // 2-3. 비교(이분탐색)
            int winCnt = compare(resultListA, resultListB);
            if (winCnt > answerWinCnt) {
                answerWinCnt = winCnt;
                answerDiceCombination = listA;
            }
        }

        Collections.sort(answerDiceCombination);
        return answerDiceCombination.stream()
                .mapToInt(integer -> integer + 1)
                .toArray();
    }

    private void combine(int depth, int start, List<Integer> list) {
        if (depth == n / 2) {
            combination.add(new ArrayList<>(list));
            return;
        }

        for (int i = start; i < n; i++) {
            list.add(i);
            combine(depth + 1, i + 1, list);
            list.remove(depth);
        }
    }

    // 재귀를 통해 결과 계산
    private void getResult(List<Integer> idxList, int idx, int sum, List<Integer> resultList) {
        if (idx == idxList.size()) {
            resultList.add(sum);
            return;
        }

        int[] oneDice = dice[idxList.get(idx)];
        for (int i = 0; i < 6; i++) {
            getResult(idxList, idx + 1, sum + oneDice[i], resultList);
        }
    }

    private List<Integer> calculateListB(List<Integer> listA) {
        List<Integer> listB = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (!listA.contains(i)) {
                listB.add(i);
            }
        }
        return listB;
    }

    private int compare(List<Integer> resultListA, List<Integer> resultListB) {
        Collections.sort(resultListA);
        Collections.sort(resultListB);

        int winCnt = 0; // 해당 주사위 조합일 때, A가 이기는 횟수

        for (Integer score : resultListA) {
            int start = 0;
            int end = resultListB.size() - 1;
            
            while (start <= end) {
                int mid = (start + end) / 2;
                if (resultListB.get(mid) < score) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            }
            
            winCnt += start;
        }

        return winCnt;
    }
}