[프로그래머스][Java][Lv. 3] 주사위 고르기

문제 설명

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

 

---

 

제한 사항

 

---

 

입출력 예

 

---

 

풀이

import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;
import java.util.PriorityQueue;

import static java.util.Map.Entry;

class Solution {
    int[] answer = {};
    int max = 0;
    
    public int[] solution(int[][] dice) {
        selectDices(new ArrayList<>(), dice, -1, dice.length / 2);
        return answer;
    }
    
    private void selectDices(List<Integer> diceIndexList, int[][] dice, int minNum, int count) {
        if (count == 0) {  // 주사위가 다 나뉘었을 때
            // 내 주사위 굴리기 시작
            PriorityQueue<Entry<Integer, Integer>> myResult = startGame(diceIndexList, 0, null, dice, true);
            
            // 상대방 주사위 굴리기 시작
            ArrayList<Integer> enemyDiceIndexList = new ArrayList<>();
            for (int i = 0; i < dice.length; i++) {
                if (!diceIndexList.contains(i)) enemyDiceIndexList.add(i);
            }
            PriorityQueue<Entry<Integer, Integer>> enemyResult = startGame(enemyDiceIndexList, 0, null, dice, false);
            
            // 나의 승리 수 구하기
            int mySum = 0, enemySum = 0;
            while (!myResult.isEmpty()) {
                Entry<Integer, Integer> myEntry = myResult.poll();
                
                while (!enemyResult.isEmpty() && enemyResult.peek().getKey() < myEntry.getKey()) {
                    enemySum += enemyResult.poll().getValue();
                }
                mySum += myEntry.getValue() * enemySum;
            }
            
            // 승리 수 높은 주사위로 갱신
            if (max < mySum) {
                max = mySum;
                answer = new int[diceIndexList.size()];
                for (int i = 0; i < diceIndexList.size(); i++) answer[i] = diceIndexList.get(i) + 1;
            }
        }
        
        // 내 주사위 선택하는 과정
        for (int i = 0; i < dice.length; i++) {
            if (minNum < i) {
                List<Integer> nextDiceIndexList = new ArrayList<>();
                nextDiceIndexList.addAll(diceIndexList);
                nextDiceIndexList.add(i);
                selectDices(nextDiceIndexList, dice, i, count - 1);
            }
        }
    }
    
    private PriorityQueue<Entry<Integer, Integer>> startGame(List<Integer> diceIndexList, int index, 
                                             Map<Integer, Integer> prevMap, int[][] dice, boolean mine) {
        // 첫 주사위일 때
        if (index == 0) {
            HashMap<Integer, Integer> nextNumCountMap = new HashMap<>();

            for (int i = 0; i < 6; i++) {
                int diceIndex = diceIndexList.get(index);
                nextNumCountMap.put(dice[diceIndex][i], nextNumCountMap.getOrDefault(dice[diceIndex][i], 0) + 1);
            }
            return startGame(diceIndexList, index + 1, nextNumCountMap, dice, mine);
        } 
        // 나머지 주사위 굴리기
        else if (index < diceIndexList.size()) {
            HashMap<Integer, Integer> numCountMap = new HashMap<>();
            HashMap<Integer, Integer> nextNumCountMap = new HashMap<>();
            
            for (int i = 0; i < 6; i++) {
                int diceIndex = diceIndexList.get(index);
                numCountMap.put(dice[diceIndex][i], numCountMap.getOrDefault(dice[diceIndex][i], 0) + 1);
            }
            for (Entry<Integer, Integer> numCountEntry : numCountMap.entrySet()) {
                for (Entry<Integer, Integer> prevEntry : prevMap.entrySet()) {
                    Integer key = numCountEntry.getKey() + prevEntry.getKey();
                    Integer value = numCountEntry.getValue() * prevEntry.getValue();
                    nextNumCountMap.put(key, nextNumCountMap.getOrDefault(key, 0) + value);
                }
            }
            return startGame(diceIndexList, index + 1, nextNumCountMap, dice, mine);
        }
        // 주사위를 전부 굴렸을 때
        else {
            PriorityQueue<Entry<Integer, Integer>> result;
            
            if (mine) result = new PriorityQueue<>((entry1, entry2) -> entry1.getKey() - entry2.getKey());
            else result = new PriorityQueue<>((entry1, entry2) -> entry1.getKey() - entry2.getKey());
            
            result.addAll(prevMap.entrySet());
            return result;
        }
    }
}

 

---

 

후기

오랜만에 3단계를 풀었더니 좀 오래 걸렸다...

 

접근 방식은 다음과 같다.

내가 가질 수 있는 주사위는 최대 5개이다. 10개 주사위 중 5개를 고르고, 상대방과의 주사위 값 경우의 수를 곱하면 엄청난 경우의 수를 계산해야 한다. 그래서 여기서 케이스를 좀 줄일 필요가 있다.

 

주사위를 고르는 과정은 자체만 놓고 보면 경우의 수가 그렇게 많지 않다. 결국 나와 상대방의 주사위를 굴려서 나온 숫자의 합 경우의 수에서 줄일 필요가 생긴다. 그런데 예제를 보면 주사위에 쓰여있는 숫자가 겹치는 경우가 있다. 333344라고 하면 결국 3과 4로만 이루어진 거고, 만약 이렇게 줄인다면 나중에 결과에서 3과 4의 개수만큼 결과에 곱해주면 된다. 그래서 Map으로 겹치는 숫자를 구해놓고, 중복 없는 숫자대로 계산하고 나중에 각 숫자마다 중복된 개수만큼 곱해주는 처리를 하면 된다.

 

내 주사위 숫자 합과 상대방 주사위 숫자 합을 구했다면 이를 오름차순으로 정렬해서 내 주사위 합보다 작은 상대방 경우를 곱하면서 계산하면 불필요한 반복을 줄일 수 있다.

 

그나저나 다른 사람 풀이를 보니 내용은 둘째치고 한눈에 들어오는데 나는 뭔가 지저분한 느낌이 있다...

어떤 차이가 있는지 고민해 봐야겠다.