[2024 KAKAO WINTER INTERNSHIP] 주사위 고르기 (C++)

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

프로그래머스

풀이

처음에는 문제를 읽고 평균, 분산 등의 통계값을 통해 정답을 구해야 하나 고민했던 문제이다.

하지만 위 통계값을 통해서는 정확한 값을 구할 수 없었고 오차가 발생하였다.

게다가 주사위의 최대 개수가 10개이므로, 모든 경우의 수를 조사해보는 것이 맞는 풀이라 생각하고 문제를 풀어나갔다.

 

먼저 주사위가 10개일 때 A가 주사위를 고르는 경우의 수는 10C3 = 252이다.

그리고 주사위 5개로 만들 수 있는 눈의 총합 경우의 수는 6^5 = 7776이다.

따라서 만약 A, B의 모든 경우의 수를 직접 비교한다면 252 * 7776 * 7776 = 15,237,476,352로 약 150억번 연산을 해야 할 것이다. 이는 약 150초의 시간이 걸리는 과정으로 적절하지 않다.

 

방법은 이진 탐색을 통해 A, B의 값을 비교하는 것이다.

먼저 A와 B의 눈의 총합 경우의 수를 정렬하고, A의 모든 경우의 수에 대하여 B의 경우의 수에 이진 탐색(Lower Bound)을 적용한다.

예를 들어 A의 경우의 수가 [2, 2, 4, 4, 6, 6]이고 B의 경우의 수가 [1, 2, 3, 4, 5, 6]일 때 A의 2를 탐색하면 B의 2의 인덱스인 1이 리턴되고 이길 수 있는 경우의 수가 1이다.

 

정렬은 O(NLogN)이므로 7776개의 리스트를 정렬하면 약 100,000번 연산이 진행된다.

그리고 이진 탐색으로 하나의 값을 찾는 데에는 O(LogN)이므로 약 13번 연산이 진행한다.

따라서 위 과정을 통해 값을 구한다면 252 * (100000 * 2 + 7776 * 13)  = 75,874,176연산이 진행되고 시간 내에 충분히 연산이 가능하다.

 

그럼에도 위 문제를 푸는 과정은 조금 까다로운데, 주사위를 고르는 것과 눈금의 합 경우의 수를 모두 구하는 과정이 조금 까다로웠다. 평소 구현을 많이 해보았다면 구현하는데 도움이 되었을 것이다.

 

코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

vector<int> answer;
int maxWins = 0;

void calculateCase(vector<vector<int>> dice, vector<int> selectedDice, int diceIndex, int answer, vector<int>& cases);
int binarySearch(int target, vector<int> vec);

void backTracking(vector<vector<int>> dice, int diceIndex, vector<int> aDice){
    if (aDice.size() == dice.size()/2){
        // b가 고른 주사위들을 고름
        vector<int> bDice;
        int aIndex = 0;
        for (int i = 0; i < dice.size(); i++){
            if (aIndex >= dice.size()/2){
                bDice.push_back(i);
            }
            else if (aDice[aIndex] == i){
                aIndex++;
            }
            else{
                bDice.push_back(i);
            }
        }

        // a와 b가 고른 주사위로 가능한 경우의 수를 구함
        vector<int> aCase, bCase;
        calculateCase(dice, aDice, 0, 0, aCase);
        calculateCase(dice, bDice, 0, 0, bCase);
        sort(aCase.begin(), aCase.end());
        sort(bCase.begin(), bCase.end());
        
        int aWins = 0;  
        for (int i = 0; i < aCase.size(); i++){
            aWins += binarySearch(aCase[i], bCase);
        }

        if (aWins > maxWins){
            maxWins = aWins;
            answer = aDice;
        }
        return;
    }
    for (int i = diceIndex; i < dice.size(); i++){
        aDice.push_back(i);
        
        backTracking(dice, i+1, aDice);
        
        aDice.pop_back();
    }
}

void calculateCase(vector<vector<int>> dice, vector<int> selectedDice, int diceIndex, int answer, vector<int>& cases){
    if (diceIndex == selectedDice.size()){
        cases.push_back(answer);
        return;
    }
    for (int i = 0; i < 6; i++){
        calculateCase(dice, selectedDice, diceIndex+1, answer+dice[selectedDice[diceIndex]][i], cases);
    }
}

int binarySearch(int target, vector<int> vec){
    int left = 0, right = vec.size()-1;
    
    while (left <= right){
        int mid = (left + right) / 2;
    
        if (vec[mid] < target){ 
            left = mid+1;
        }
        else{
            right = mid-1;
        }
    }
    return left;
}


vector<int> solution(vector<vector<int>> dice) {
    backTracking(dice, 0, {});
    
    for (int i = 0; i < answer.size(); i++){
        answer[i]++;
    }
    return answer;
}