[프로그래머스] 주사위 고르기 - 조합(Combination) + 브루트포스(BruteForce) + 이진탐색(Binary Search) JAVA

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

프로그래머스

코드설명

조합(Combination) + 브루트포스(BruteForce) + 이진탐색(Binary Search) 를 활용하는 문제입니다.

 

문제 접근을 어떻게 할것이느냐에 따라 푸는데 걸리는 시간이 획기적으로 차이납니다.

일반적인 문제에서는 구현을 어떻게할지 그대로 구현하면 되는경우가 많습니다.

이 문제 같은경우, 문제에 숨어있는 의도 혹은 빠르게 풀 수 있는 단서를 찾고서 바로 풀어야합니다. 

 

문제에서 숨어있는 의도는

1. 주사위는 2개이니 한개의 조합만 구하면 나머지 주사위는 알아서 구해집니다.
2. 모든 경우를 Table 형식으로 만들어서 관리하려하지말고, 순간순간 구하면서 진행해야합니다.
3. 승무패에서 "승"만 구하면 됩니다.

2번이 무슨말인지 상당히 헷갈립니다. 예로 들면, "#1 #2" 의 주사위가 나올 수 있는 경우를 모두 구하고서 마지막에 전체 승률을 구한다고 하면 상당히 복잡해집니다. 저같은 경우 처음에 StringBuilder로 직접 각 조합과 String[] "#1 #2" 이런식으로 각 인덱스가 어떤 조합을 가리키는지 처리하는 방식으로 진행했다가 구현하는데 많은 시간이 걸렸습니다.

 

대신에, 각 조합을 구할때마다 구하면서 진행한다면 매핑 변수('#1 #2')를 사용하지 않아 훨씬 문제가 단순화됩니다. 

 

또한, 위의 사항을 활용하여 구현을 완료하더라도 시간초과가 다시 발생했습니다.

 

이유는 아래의 예로 설명해보겠습니다. 

최악의 경우로 가정해보겠습니다.

만약 10개의 주사위 일경우, 총 10C5 = 252 개의 조합이 나올 수 있습니다.

하나의 비교 당 6^5 * 6^5 = 60,466,176 숫자의 연산이 나옵니다.

즉, 6^10 * 252 = 15,237,476,352 으로 150억의 연산이 필요합니다.

일반적으로 1억 당 1초 이니 150초가 걸립니다.

 

주사위 조합을 구하는데 걸리는 시간복잡도는 줄일 수 없고, 주사위의 경우에서 시간을 줄여야만 합니다.

 

방법은, 문제에서 예시 1번의 주사위 #1 #2 인 경우에서 앞의 6번 연산만 진행해보겠습니다.

주사위 "#1 #2"가 던져졌을떄 {4, 4, 4, 4, 5, 5 .... } 36개.

주사위 "#3 #4"가 던져졌을떄 {2, 2, 4, 4, 4, 4, .... } 36개 가 나올 것 입니다.

 

이떄 주사위 "#1 #2"의 0번쨰 인덱스인 4가 주사위 "#3 #4"의 모든 행을 도는 것으로 인해 시간초과가 발생합니다.

이떄 그 대신에 4는 { 2 2 4 4 4 4 ... } 에서 4 보다 작은 숫자 중에서 가장 큰 Index를 이진탐색으로 찾습니다.

그렇게 되면 그 수만큼 해당 주사위가 "승리"합니다.  

 

하나의 숫자를 찾는데 이진탐색의 시간복잡도는 O(log n) 이므로 O(log 36) 으로 획기적으로 줄어듭니다.

코드

한번에 (#1, #2), (#3, #4) 와 (#3, #4), (#1, #2) 를 연산하면서 계산 하는 부분을 2배 줄였습니다.

속도는 가장 빠른 코드입니다.

import java.util.*;
class Solution {
    int[][] Dice;
    int[] answer;
    int DiceLength;
    
    ArrayList<int[]> combA = new ArrayList<int[]>();
    ArrayList<int[]> combB = new ArrayList<int[]>();
    
    ArrayList<Integer> scoreA = new ArrayList<Integer>();
    ArrayList<Integer> scoreB = new ArrayList<Integer>();
    
    int maxWinCnt = 0;
    public int[] solution(int[][] dice) {
        Dice = dice;
        DiceLength = dice.length;
        
        getComb(0, 0, new int[DiceLength / 2]);

		//A가 뽑는 모든 조합에 대해서 주사위 점수를 비교합니다.
        //이떄 중복되서 계산하는 부분이 있습니다만, 시간초과는 발생하지 않습니다.
        for(int i=0;i<combA.size()/2;i++){
            int[] combAStore = combA.get(i);
            
            boolean[] visited = new boolean[DiceLength];
            for(int j=0; j<combAStore.length; j++){
                visited[combAStore[j]] = true;
            }
            
            int[] combBStore = new int[DiceLength / 2];
            int combBStoreIdx = 0;
            for(int j=0;j<DiceLength; j++){
                if(visited[j] == false){
                    combBStore[combBStoreIdx++] = j;
                }
            }
            scoreA.clear(); scoreB.clear();
            calculateScore(0, 0, combAStore, scoreA);
            calculateScore(0, 0, combBStore, scoreB);
            
            Collections.sort(scoreA);
            Collections.sort(scoreB);
            int localWinCnt = 0;
            
            for(int j=0;j<scoreA.size();j++){
                //잘못 계산한경우이다. 이긴경우를 더해야합니다.
                // localWinCnt += scoreA.size() - binarySearch(0, scoreA.size() - 1, scoreB, scoreA.get(j)) + 1;
                localWinCnt += binarySearch(0, scoreA.size() - 1, scoreB, scoreA.get(j)) + 1;
                // System.out.println();
            }
            
            if(maxWinCnt < localWinCnt){
                maxWinCnt = localWinCnt;
                answer = combAStore.clone();
            }
            
            localWinCnt = 0;
            for(int j=0;j<scoreB.size();j++){
                //잘못 계산한경우이다. 이긴경우를 더해야합니다.
                // localWinCnt += scoreA.size() - binarySearch(0, scoreA.size() - 1, scoreB, scoreA.get(j)) + 1;
                localWinCnt += binarySearch(0, scoreA.size() - 1, scoreA, scoreB.get(j)) + 1;
            }
            if(maxWinCnt < localWinCnt){
                maxWinCnt = localWinCnt;
                answer = combBStore.clone();
            }
            
        }
        
        for(int i=0;i<DiceLength/2;i++){
            answer[i] += 1;
        }
        return answer;
    }
    
    
public int binarySearch(int start, int end, ArrayList<Integer> arr, int targetNum){
        
        int left = 0, right = end;
        
        while(left <= right){
            int middle = (left + right) / 2;
            //만약 목표 num이 더 작은 경우에도 right = middle - 1 로 처리하여 해당 숫자가 질 수 있는 경우의 수를 구한다.
            if(targetNum <= arr.get(middle)){
                right = middle - 1;          
            } else if(targetNum > arr.get(middle)){
                left = middle + 1;
            }
        }
        return right;
    }
    
    public void calculateScore(int level, int sum, int[] selectedDice, ArrayList<Integer> Target){
        if(level == DiceLength / 2){
            Target.add(sum);
            return ;
        }
        for(int i=0;i<6;i++){
            calculateScore(level + 1, sum + Dice[selectedDice[level]][i], selectedDice, Target);
        }
        
    }
    
    public void getComb(int level, int idx, int[] selected){
        //절반을 선택했다면,
        if(level == DiceLength / 2){
            combA.add(selected.clone());
            // combA.add(selected); 배열은 참조값으로 들어가기에 clone을 해주어야합니다.
            return ;
        }
        
        for(int i = idx; i < DiceLength; i++){
            selected[level] = i;
            getComb(level + 1, i + 1, selected);
            selected[level] = 0;
        }
    }
}

 

처음에 이분탐색을 활용하지 않고,  각 금액을 모두 비교했던 경우입니다.

import java.util.*;
class Solution {
    int[][] Dice;
    int[] answer;
    int DiceLength;
    
    ArrayList<int[]> combA = new ArrayList<int[]>();
    ArrayList<int[]> combB = new ArrayList<int[]>();
    
    ArrayList<Integer> scoreA = new ArrayList<Integer>();
    ArrayList<Integer> scoreB = new ArrayList<Integer>();
    
    int maxWinCnt = 0;
    public int[] solution(int[][] dice) {
        Dice = dice;
        DiceLength = dice.length;
        
        getComb(0, 0, new int[DiceLength / 2]);
        
        //A가 뽑는 모든 조합에 대해서 주사위 점수를 비교합니다.
        //이떄 중복되서 계산하는 부분이 있습니다만, 시간초과는 발생하지 않습니다.
        for(int i=0;i<combA.size();i++){
            int[] combAStore = combA.get(i);
            
            boolean[] visited = new boolean[DiceLength];
            for(int j=0; j<combAStore.length; j++){
                visited[combAStore[j]] = true;
            }
            
            int[] combBStore = new int[DiceLength / 2];
            int combBStoreIdx = 0;
            for(int j=0;j<DiceLength; j++){
                if(visited[j] == false){
                    combBStore[combBStoreIdx++] = j;
                }
            }
            scoreA.clear(); scoreB.clear();
            calculateScore(0, 0, combAStore, scoreA);
            calculateScore(0, 0, combBStore, scoreB);
            
            int localWinCnt = 0;
            for(int j=0;j<scoreA.size();j++){
                for(int k=0;k<scoreB.size();k++){
                    if(scoreA.get(j) > scoreB.get(k)){
                        localWinCnt += 1;
                    }
                }
            }
            if(maxWinCnt < localWinCnt){
                maxWinCnt = localWinCnt;
                answer = combAStore.clone();
            }
        }
        
        for(int i=0;i<DiceLength/2;i++){
            answer[i] += 1;
        }
        return answer;
    }
    
    public void calculateScore(int level, int sum, int[] selectedDice, ArrayList<Integer> Target){
        if(level == DiceLength / 2){
            Target.add(sum);
            return ;
        }
        for(int i=0;i<6;i++){
            calculateScore(level + 1, sum + Dice[selectedDice[level]][i], selectedDice, Target);
        }
        
    }
    
    public void getComb(int level, int idx, int[] selected){
        //절반을 선택했다면,
        if(level == DiceLength / 2){
            combA.add(selected.clone());
            // combA.add(selected); 배열은 참조값으로 들어가기에 clone을 해주어야합니다.
            return ;
        }
        
        for(int i = idx; i < DiceLength; i++){
            selected[level] = i;
            getComb(level + 1, i + 1, selected);
            selected[level] = 0;
        }
    }
}