99클럽 코테 스터디 26일차 - 프로그래머스 , 주사위 고르기

문제 풀이 예상 시간보다 지나가면 다른 해석을 보고 있습니다. 

문제

풀이

문제 해석

1. 짝수개의 주사위가 주어진다. 주사위는 1~n까지의 번호를 가지고 있고 정육면체 주사위고 각 면이 나올 확률은 같다.

2. A는 먼저 주사위를 절반 가져갈 수 있다.

3. 가져간 주사위를 모두 돌려서 나오는 값들의 합이 큰 사람이 이긴다.

4. A는 먼저 주사위를 가져갈 수 있기 때문에 어떻게 가져가야 이길 수 있는지 주사위 번호를 1차원 배열로 오름차순 출력해라

5. 각 주사위의 면의 원소는 1~100까지이다.

문제 풀이

1. 기업기출문제 답게 복합 알고리즘을 사용해야 한다.

2. 주사위를 선택하는 과정을 백트래킹을 선택

3. 그 후에 선택된 주사위(A)와 선택되지 않은 주사위(B)들의 합을 구하는 과정 DFS 선택

4. 주사위 합 List들에서 A리스트의 각 값이 B리스트의 값들보다 큰 경우를 찾을 때 이분탐색을 사용

5. 승리하는 경우가 클 때만 값을 변경 해준다.

소스코드

import java.util.*;
class Solution {
    int goal;
    int len;
    int victory = 0;
    int[] select;
    boolean[] visited;
    int[] answer;
    int[][] dice2;

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

        //전역변수 선언
        dice2 = dice;
        len = dice.length;
        goal = len/2;
        visited = new boolean[len];
        select = new int[goal];
        answer = new int[goal];

        //주사위 선택 및 완탐
        findCombi(0, 0);

        return answer;
    }

    private void findCombi(int cnt, int start){
        if(cnt == goal){
            //각 주사위들의 합 가져오기
            List<Integer>[] lists = getSum(select);
            List<Integer> listA = lists[0];
            List<Integer> listB = lists[1];

            //A가 승리하는 경우 가져오기
            int vic = getVictory(listA, listB);

            if(victory < vic){
                victory = vic;
                for (int i = 0; i < goal; i++) {
                    answer[i] = select[i] + 1;
                }
            };
            return;
        }
        for(int i=start;i<len;i++){
            if(visited[i]) continue;
            visited[i] = true;
            select[cnt] = i;
            dfs(cnt+1, i + 1);
            visited[i] = false;
        }
    }

    private int getVictory(List<Integer> listA, List<Integer> listB) {
        int vic = 0;
        int[] val = new int[listA.get(listA.size()-1) + 1];
        for (int x : listA) {
            if(val[x] != 0){
                vic += val[x];
                continue;
            }
            // 이분탐색으로 listB에서 x보다 큰 값들의 시작 인덱스를 찾음
            int lt = 0;
            int rt = listB.size();
            while (lt < rt) {
                int mid = (lt + rt) / 2;
                if (listB.get(mid) < x) {
                    lt = mid + 1; // 더 작은 범위를 탐색
                } else {
                    rt = mid; // 더 큰 범위를 탐색
                }
            }
            
            vic += lt;
            val[x] = lt;
        }
        return vic;
    }

    private List<Integer>[] getSum(int[] select) {
        List<Integer> listA = new ArrayList<>();
        List<Integer> listB = new ArrayList<>();

        // 선택된 주사위 
        Set<Integer> selectedIndices = new HashSet<>();
        for (int idx : select) {
            selectedIndices.add(idx);
        }

        // A 조합 생성
        generateSums(0, 0, selectedIndices, true, listA);

        // B 조합 생성
        generateSums(0, 0, selectedIndices, false, listB);

        // 정렬
        Collections.sort(listA);
        Collections.sort(listB);

        return new List[]{listA, listB};
    }

    private void generateSums(int currentIndex, int currentSum, Set<Integer> selectedIndices, boolean isA, List<Integer> resultList) {
        if (currentIndex == len) {
            resultList.add(currentSum);
            return;
        }

        // 선택된 주사위를 처리할지 나머지 주사위를 처리할지 결정
        boolean belongsToCurrentSet = selectedIndices.contains(currentIndex);
        if ((isA && belongsToCurrentSet) || (!isA && !belongsToCurrentSet)) {
            for (int faceValue : dice2[currentIndex]) {
                generateSums(currentIndex + 1, currentSum + faceValue, selectedIndices, isA, resultList);
            }
        } else {
            generateSums(currentIndex + 1, currentSum, selectedIndices, isA, resultList);
        }
    }

}

TIL

• 복합 알고리즘 문제들은 초반 알고리즘들은 쉽게 찾을 수 있는데 깊숙히 들어갔을 때 사용하는 알고리즘을 찾기가 쉽지 않다. 기출문제를 반복 숙달해야겠다.