[JAVA] 프로그래머스 level3 주사위 고르기

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

프로그래머스

 

코딩테스트 연습 > 2024 KAKAO WINTER INTERNSHIP > 주사위 고르기 

 

문제 접근 

해당 문제는 완전탐색, 이분탐색을 조합해서 문제를 풀었다. 

 

주사위가 짝수로 주어지고 A가 주어진 주사위 N/2개 B가 주어진 주사위 N/2개를 고른다. 

각 주사위는 일반적인 주사위와 다르게 숫자가 랜덤하다. 또한 중복된 숫자도 있다.

 

#1 [1, 2, 3, 4, 5, 6]
#2 [3, 3, 3, 3, 4, 4]
#3 [1, 3, 3, 4, 4, 4]
#4 [1, 1, 4, 4, 5, 5]

 

해당 케이스를 중점으로 코드 설명을 하겠다.

 

주사위가 4개 있으면 주사위를 고를 수 있는 조합은 6가지가 나온다. 

A[1,2] B[3,4]

A[1,3] B[2,4]

A[1,4] B[2,3]

A[2,3] B[1,4]

A[2,4] B[1,3]

A[3,4] B[1,2]

 

완전탐색을 통해서 조합을 구한다.

 static int [] memo = new int [size/2];
 func(0, 1) 
 
 public static void func1(int depth, int cur){
        if(depth == size/2){
            func2(memo);
            return;
        }
        for(int i = cur; i <= size; i++){
            memo[depth] = i;
            func1(depth + 1, i + 1);
        }
 }

func(0,1)으로 시작하면 

재귀함수인 func1이 돌면서 

memo 배열에는 다음과 같은 순서대로 값이 들어간다. 

 

[1,2]

[1,3]

[1,4]

[2,3]

[2,4]

[3,4]

 

여기서 중요한 점은 'A를 중점으로 생각하자' 이다 

A가 1,2를 선택하면 B는 자연스럽게 3,4를 선택해야 한다. 

그리고 A의 조합을 구하면 결국 B에서 필요한 조합 또한 구해진다. 

 

A와 B의 대결 구도는 

 

주사위가 2개

A의 1번 주사위를 1번 굴린 값 VS B의 1번 주사위를 1번 굴린 값

 

주사위가 4개

A의 1번 주사위를 1번 굴린 값과 + A의 2번 주사위를 굴린값 

VS

B의 1번 주사위를 1번 굴린 값과 + B의 2번 주사위를 굴린값 

 

주사위가 2개인 경우 나오는 경우의 수는 6 * 6 = 36 

주사위가 4개인 경우 나오는 경우의 수는 6 * 6 * 6 * 6 = 1296 이다. 

 

우린 이미 주사위 조합의 경우의 수를 구했으니까

각 조합이 나오는 경우의 수를 구하면 된다. 

 

이 또한 완전탐색을 통해서 조합을 구한다. 

public static void func2(int[] input){
    int [] temp = Arrays.copyOf(input, input.length);
    map.put(temp, new ArrayList<>());
    func3(input, 0, 0, temp);
}
public static void func3(int[] input, int depth, int sum, int[] temp){
     if(depth == size/2){
         map.get(temp).add(sum);
         return;
     }
     for(int i = 0; i < 6; i++){
          func3(input, depth + 1, sum + d[input[depth]-1][i], temp);    
     }
}

 

여기서 중요한 점은 조합을 기록하는 map의 key이다.

각 key는 배열 자체이다. 

ex) key: [1,2] value: ArrayList(1번 주사위와 2번 주사위를 굴려서 나오는 sum 값들)

 

컬렉션에는 값이 일반값이 아닌 객체 값만 담을 수 있는데 배열 또한 객체이다. 

 

이제 우리는 모든 조합에 대한 값들을 구했다. 

그럼 이제 대결(A VS B)을 하면 된다. 

 

이건 이분 탐색을 통해서 해결했다.

이분 탐색을 사용하지 않으면 

A 조합값이 B에 있는 조합보다 큰지 이중 for문을 돌려서 구해야 하는데 

 

제한 사항을 보면 주사위는 최대 10개까지 있다. 

그럼 1개의 조합에 6^5개의 경우의 수가 나온다.

 

이분 탐색을 사용하면 252 * 6^5 * log(6^5)

이중 for문은 252 * 6^5 * 6^5 

 

계산하면 어마어마한 차이인 걸 알 수 있다 

 

 그리고 이분탐색을 시작하기 전에는 딱 2가지만 주의하면 된다.

 

 map에 저장된 key 배열에 같은 값이 있으면 안된다. 

 A[1,2] B[1,4] 올바르지 않은 경우이다. A가 1을 골랐는데 B가 1을 또 고를 수는 없다.  

 

 정렬을 꼭 하자 정렬을 하지 않고 이분 탐색을 하면 이상한 결과가 나온다.

전체 코드

import java.util.*;
import java.util.stream.*;
class Solution {
    static int size;     // 주사위 개수 
    static int [][] d;   // 완전탐색에 사용할 dice copy
    
    static int [] memo;
    
    static HashMap<int[], ArrayList<Integer>> map = new HashMap<>(); // 조합 기록 맵
    
    public int[] solution(int[][] dice) {
        size = dice.length;
        
        d = new int [size][6];
        // 완전탐색에 사용할 dice copy
        for(int i = 0; i < size; i++){
            d[i] = Arrays.copyOf(dice[i], 6);
        }
        
        // 주사위 조합 구하기 func1 
        memo = new int [size/2];
        func1(0, 1);
        
        int max = 0;
        int [] answer = new int [size/2];
        
        List<int[]> list = map.keySet().stream().collect(Collectors.toList());
        
        // 정렬 또한 시간을 많이 잡아 먹는다. 정렬을 했는지 체크 용도 set 
        Set<Integer> set = new HashSet<>();
        
        for(int i = 0; i < list.size(); i++){
            int [] key = list.get(i);
            for(int j = 0; j < list.size(); j++){
                 if(i == j) continue;
                 int [] key2 = list.get(j);
                 boolean flag = true;
                 
                 // 조합 검증 로직 
                 for(int k = 0; k < key.length; k++){
                     for(int l = 0; l < key2.length; l++){
                         if(key[k] == key2[l]){
                             flag = false;
                             break;
                         }
                     }
                     if(!flag) break;
                 }
                 if(!flag) continue;
             
                 ArrayList<Integer> compare1 = map.get(key);
                 ArrayList<Integer> compare2 = map.get(key2);
                 
                 // 정렬 검증 로직 
                 if(!set.contains(i)){
                     Collections.sort(compare1);
                     set.add(i);
                 }
                 if(!set.contains(j)){
                     Collections.sort(compare2);
                     set.add(j);
                 }
                
                 // 이분탐색 시작 
                 int win = 0;
                 for(int k = 0; k < compare1.size(); k++){
                     int target = compare1.get(k);
                     
                     int start = 0;
                     int end   = compare1.size();
                     while (start < end){
                         int mid = (start + end) / 2;
                         if(target <= compare2.get(mid)){
                             end = mid;
                         }
                         else start = mid + 1;
                     }
                     win += end; 
                 }
                 // 승수가 가장 많은 조합을 answer에 기록 
                 if(max < win){
                     answer = key; 
                     max = win;
                 }
            }
        }
        
        return answer;
    }

    public static void func1(int depth, int cur){
        if(depth == size/2){
            // 해당 주사위를 통해서 주사위 조합 구하기 func2, func3
            func2(memo);
            return;
        }
        for(int i = cur; i <= size; i++){
            memo[depth] = i;
            func1(depth + 1, i + 1);
        }
    }
    public static void func2(int[] input){
        int [] temp = Arrays.copyOf(input, input.length);
        // 배열 자체를 key에 넣기 
        map.put(temp, new ArrayList<>());
        func3(input, 0, 0, temp);
    }
    public static void func3(int[] input, int depth, int sum, int[] temp){
         if(depth == size/2){
             map.get(temp).add(sum);
             return;
         }
         for(int i = 0; i < 6; i++){
              func3(input, depth + 1, sum + d[input[depth]-1][i], temp);    
         }
    }
}

1. 주사위 고르

 

1. 위

 

1. 주 고