[프로그래머스/C++] 알고리즘 - 주사위 고르기

안녕하세요! 테크지니어22입니다.

오늘은 프로그래머스 알고리즘 주사위 고르기를 풀어보도록 하겠습니다.

 

[문제 접근]

처음에는 for문으로 묵묵히 풀었습니다. 그러나 시간초과가 발생했습니다. 시간복잡도를 줄여야 한다는 것을 느꼈고, 어떤 알고리즘을 이용해야할지 생각했습니다. 가장 만만한게 이분 탐색이었는데 왜 이분 탐색을 써야하는지 당위성을 찾지 못했습니다. 이후 도움을 받았는데 아래의 예제표를 보고 어떤 알고리즘을 풀어야할 지 생각해보라는 힌트를 얻었습니다.

열을 보았을 때 b의 값보다 큰 a값이 나오는 순간만 찾으면 B가 특정값일때 이 값보다 큰 A의 값들의 개수를 셀 수 있습니다. 이를 통해 이분 탐색의 upper_bound 개념을 떠올릴 수 있었고 이를 활용하여 문제를 풀었습니다.

[풀이 전략]

1. 주사위에 번호를 매겨 dice_kind에 저장합니다.

2.조합에 사용할 0과 1로 구성된 벡터를 구성하고, permutation + do while을 구성합니다.

3. a와 b가 가져갈 주사위를 배분합니다.

4. a와 b는 정확히 절반씩 나누어 갖기 때문에, 6^n말고 6^(n-1) 경우만 확인합니다.

5. 10진법을 6진법으로 바꾸는 함수를 생성합니다.

6. 5를 이용하여 각 주사위로 뽑은 번호들의 합은 a와 b 각각 구한 다음에 asum_tot와 bsum_tot에 삽입합니다.

7. 이분탐색을 이용하여 a의 합이 b의 합보다 큰 경우를 셉니다.

8. 7에서 센 개수를 max_cnt와 비교하여 크면 max_cnt를 업데이트하고 answer에 a로 대치합니다.

 

[코드]

#include <string>
#include <vector>
#include <algorithm>
using namespace std;


vector<int> decimalToBase6(int decimal,int n ) {
        vector<int> result(n) ;
    int index = n -1 ;
    while (decimal > 0) {
        int remainder = decimal % 6;
        result[index] = remainder;
        decimal /= 6;
        index--;
    }
    return result;
}

vector<int> solution(vector<vector<int>> dice) {
    vector<int> answer;
    vector<int> dice_kind ;
    vector<int> tmp ;
    int max_cnt = 0 ; 
    int dice_cnt = dice.size();
    
    for(int i = 1 ; i <= dice_cnt ; i++){
        dice_kind.push_back(i);
        
        if( i <= dice_cnt / 2) {
            tmp.push_back(1); 
        } else { tmp.push_back(0);}
    }
    
    do{     
        cout << "a";
        vector<int> a ; 
        vector<int> b ;
        for(int i = 0; i < dice_cnt; i++){
            if(tmp[i] == 1) {
                // A 주사위
                a.push_back(dice_kind[i]);
            } else {
                // B 주사위
                b.push_back(dice_kind[i]);
            }
        }
        int tot_cnt = 1;
        for(int i = 0 ; i < dice_cnt/2  ; i++) tot_cnt *= 6;

        
            vector<int> asum_tot, bsum_tot ; 

            for(int j = 0 ; j < tot_cnt ; j++) {
                  auto t = decimalToBase6(j,dice_cnt/2);       
                  int a_sum = 0 ;
                  int b_sum = 0 ;
            

            for(int l = 0 ; l < dice_cnt/2 ; l++){
                a_sum += dice[a[l]-1][t[l]];
                b_sum += dice[b[l]-1][t[l]];
            }
            asum_tot.push_back(a_sum);
            bsum_tot.push_back(b_sum);
        }      
            sort(asum_tot.begin(), asum_tot.end());
	        sort(bsum_tot.begin(), bsum_tot.end());
        
        int tmp_cnt = 0 ;
        for(int i = 0 ; i < bsum_tot.size() ; i++) {
            tmp_cnt += asum_tot.end() - upper_bound(asum_tot.begin(), asum_tot.end(), bsum_tot[i]);
        }
        
        if(max_cnt < tmp_cnt) {
            max_cnt = tmp_cnt ;
            answer = a; 
        }
    } while(prev_permutation(tmp.begin(),tmp.end()));
    return answer;
}

[배울 점]

- permutation함수 사용법 미숙

   -> 항상 정렬을 하고 사용해야하고 조합을 할거면 파라미터로 1과 0로 구성된 벡터를 대입하기.

   -> next랑 prev 사용법 숙지.

- 예제를 잘 살펴보고 패턴, 규칙을 살펴보고 어떤 알고리즘 개념을 이용해야할 지 유추하기. -> 단순 for문 밖에 생각나지 않는데 시간복잡도를 줄여야하는 상황에 좋음.