주사위 고르기 [Lv.3]

코딩테스트 연습 - 주사위 고르기 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

N개의 주사위가 있고 A와 B가 N/2개의 주사위를 가져갑니다.

이후 A, B가 주사위를 모두 던져서 높은 숫자가 나온 쪽이 이기는 게임을 하게 되는데

어떤 주사위를 가져가야 이길 확률이 높은지 찾는 문제입니다!

 

풀이 방법

우선 이 문제는 모든 경우의 수에 대해서 탐색 후 승리 횟수를 기록해야 합니다.

그렇기 위해서는

1. 모든 주사위 조합의 경우의 수를 찾는다 (1, 2 주사위 1, 3 주사위, 1, 4 주사위 .. . . . . .)

2. 모든 주사위를 던져서 나올 수 있는 수를 모두 구한다.

3. 상대의 주사위에서 나올 수 있는 모든 수를 구한다.

4. 비교 후 승리 횟수를 카운트 한다.

 

"주사위의 모든 경우의 수를 찾는 부분"과 "비교하는 부분"에서 속도가 느려 틀릴 가능성이 높습니다.

이 부분에서 주의하여 코드를 짜야합니다.

 

1번 주사위의 모든 경우의 수 찾기

void GenerateDiceSets(vector<int>v, vector<bool> visited, int size)
{
    if (v.size() == size / 2)
    {
        _diceSet.push_back(v);
        return;
    }
    
    for (int i = 0; i < size; i++)
    {
        if (visited[i])
            continue;
        
        visited[i] = true;
        
        vector<bool> newB = visited;
        vector<int> newV = v;
        newV.push_back(i);
        
        GenerateDiceSets(newV, newB, size );
    }
}

호출 -> GenerateDiceSets(vector<int>(), vector<bool>(dice.size()), dice.size());

 

주사위 세트를 찾는 경우의 수를 구하는 코드 입니다.

4개의 주사위가 있다면 (01, 02, 03, 12, 13, 23)을 _diceSet에 담아줍니다.

 

void GenerateDiceCombis(vector<int>v, int size, int start = 0)
{
    if (v.size() == size / 2)
    {
        _diceCombi.push_back(v);
        return;
    }
     
    for (int i = start; i < 6; i++)
    {
        vector<int> newV = v;
        newV.push_back(i);
        
        GenerateDiceCombis(newV, size, start);
    }
}

주사위 조합을 찾는 경우의 수를 구하는 코드입니다.

내가 가지고 있는 주사위를 던질 때 나올 수 있는 모든 경우의 수를 구해줍니다.

2개가 있다면 (11, 12, 13, 14, 15, 16, 21, 22, 23, 24, 25, 26, 31, 32, 33, 34, 35, 36, 41, 42, 43, 44, 45, 46..........)

 

2번 주사위를 던져서 나올 수 있는 모든 수 찾기

for (auto diceSet : _diceSet)
{
    vector<int> numbers;
    for (auto c : _diceCombi)
    {
        int temp = 0;
        for (int i = 0; i < c.size(); i++)
        {
            int diceID = diceSet[i];
            int diceNum = c[i];
            temp += dice[diceID][diceNum];
        }
        numbers.push_back(temp);
    }
    sort(numbers.begin(), numbers.end());
    _diceNumbers.push_back(numbers);
}

1. _diceSet에서 현재 다이스 세트를 가져옵니다. ex( 1, 2, 3 번 주사위 )

2. _diceCombi에서 주사위를 모두 던졌을 때 나올 수 있는 경우의 수를 가져옵니다. ex(1, 5, 3 )

-> 1번 주사위 1번 눈금,   

-> 2번 주사위 5번 눈금,   

-> 3번 주사위 3번 눈금

 

3. 다이스 세트에서 추출한 현재 주사위 Index와 현재 눈금을 이용하여 숫자를 찾고 temp에 더해줍니다.

4. 구한 숫자 (temp)를 numbers에 넣어줍니다.

5. numbers를 정렬 후 _diceNumbers에 넣어서 관리합니다.

-> _diceSet[i]에서 나올 수 있는 수는 _diceNumbers[i]에 저장됩니다.

 

3번 상대의 주사위에서 나올 수 있는 모든 수 찾기

상대의 주사위에서 나올 수 있는 모든 수도 똑같이 계산하게 된다면 시간이 너무 오래걸리게 됩니다.

계산 없이 1의 속도로 찾는 방법이 있습니다.

_diceSet를 구하는 코드에서 경우의 수를 순서대로 배열에 넣어주었던 것을 기억할 것입니다.

array = {
    123, 124, 125, 126, 134, 135, 136, 145, 146, 156, 
    234, 235, 236, 245, 246, 256, 345, 346, 356, 456
};

- 주사위를 3개 가질 수 있을 때의 경우의 수 입니다 ( 총 20개 )

배열의 시작을 0, 끝을 19로 하겠습니다.

 

나의 주사위가 0번일 때 (123) 상대의 주사위는 19(456) 이어야 합니다.

나의 주사위가 1번일 때 (124) 상대의 주사위는 18(356) 이어야 합니다.

나의 주사위가 2번일 때 (125) 상대의 주사위는 17(346) 이어야 합니다.

.

.

. 

나의 주사위가 13번일 때 (245) 상대의 주사위는 6(136) 이어야 합니다.

즉 나의 주사위가 i일때 상대의 주사위는

 _diceSet.size() - 1 - i

 

4번 비교 후 승리 횟수 카운트

비교하는 과정에서 N^2의 속도로 하게되면 시간 초과의 위험이 있습니다.

이럴 때 쓸 수 있는 방법은 이진 탐색 이용하는 것 입니다. 

int compare(int a, int b)
{
    int result = 0;
    
    for (int cur : _diceNumbers[a])
    {
        int start = 0;
        int end = _diceNumbers[b].size() - 1;
        while (start <= end)
        {
            int mid = (start + end) / 2;

            if (_diceNumbers[b][mid] >= cur){
                end = mid - 1;
            }

            else{
                start = mid + 1;
            }
        }
        result += start;
    }

    return result;
}

 

이전에 _diceNumbers에 배열을 넣기전 sort함수로 정렬을 했었는데, 그 이유가 여기에 있습니다.

이진 탐색으로 "cur"를 타겟 배열과 비교하여 index를 LogN의 속도로 찾아주는 코드입니다.

예를 들어 cur이 타겟 배열의 15번 index에 들어갔다면 그 아래의 인덱스들 14개는 이기는 것을 의미합니다.

 

 

정답 코드

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

using namespace std;

vector<vector<int>> _diceSet;
vector<vector<int>> _diceCombi;
vector<vector<int>> _diceNumbers;

void GenerateDiceSets(vector<int>v, vector<bool> visited, int size)
{
    if (v.size() == size / 2)
    {
        _diceSet.push_back(v);
        return;
    }
    
    for (int i = 0; i < size; i++)
    {
        if (visited[i])
            continue;
        
        visited[i] = true;
        
        vector<bool> newB = visited;
        vector<int> newV = v;
        newV.push_back(i);
        
        GenerateDiceSets(newV, newB, size );
    }
}

void GenerateDiceCombis(vector<int>v, int size, int start = 0)
{
    if (v.size() == size)
    {
        _diceCombi.push_back(v);
        return;
    }
     
    for (int i = start; i < 6; i++)
    {
        vector<int> newV = v;
        newV.push_back(i);
        
        GenerateDiceCombis(newV, size, start);
    }
}

int compare(int a, int b)
{
    int result = 0;
    
    for (int cur : _diceNumbers[a])
    {
        int start = 0;
        int end = _diceNumbers[b].size() - 1;
        while (start <= end)
        {
            int mid = (start + end) / 2;

            if (_diceNumbers[b][mid] >= cur){
                end = mid - 1;
            }

            else{
                start = mid + 1;
            }
        }
        result += start;
    }

    return result;
}

vector<int> solution(vector<vector<int>> dice) {

  GenerateDiceSets(vector<int>(), vector<bool>(dice.size()), dice.size());
  GenerateDiceCombis(vector<int>(), dice.size() / 2);
    
    for (auto diceSet : _diceSet)
    {
        vector<int> numbers;
        for (auto c : _diceCombi)
        {
            int temp = 0;
            for (int i = 0; i < c.size(); i++)
            {
                int a = diceSet[i];
                temp += dice[a][c[i]];
            }
            numbers.push_back(temp);
        }
        sort(numbers.begin(), numbers.end());
        _diceNumbers.push_back(numbers);
    }

    
    int maxId = 0;
    vector<int> v(_diceSet.size());
    for (int i = 0; i < _diceSet.size(); i++)
    {
        int target = _diceSet.size() - i - 1;
        v[i] = compare(i, target);
        
        if (v[maxId] < v[i])
            maxId = i;
    }
            
    for (int& i : _diceSet[maxId])
        ++i;
    
    return _diceSet[maxId];
}