(2024 KAKAO WINTER INTERNSHIP) 주사위고르기

문제 설명

A와 B가 n개의 주사위를 가지고 승부를 합니다. 주사위의 6개 면에 각각 하나의 수가 쓰여 있으며, 주사위를 던졌을 때 각 면이 나올 확률은 동일합니다. 각 주사위는 1 ~ n의 번호를 가지고 있으며, 주사위에 쓰인 수의 구성은 모두 다릅니다.

 

A가 먼저 n / 2개의 주사위를 가져가면 B가 남은 n / 2개의 주사위를 가져갑니다. 각각 가져간 주사위를 모두 굴린 뒤, 나온 수들을 모두 합해 점수를 계산합니다. 점수가 더 큰 쪽이 승리하며, 점수가 같다면 무승부입니다.

 

A는 자신이 승리할 확률이 가장 높아지도록 주사위를 가져가려 합니다.

 

다음은 n = 4인 예시입니다.

 

주사위  구성

#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]

 

예를 들어 A가 주사위 #1, #2를 가져간 뒤 6, 3을 굴리고, B가 주사위 #3, #4를 가져간 뒤 4, 1을 굴린다면 A의 승리입니다. (6 + 3 > 4 + 1)

A가 가져가는 주사위 조합에 따라, 주사위를 굴린 1296가지 경우의 승패 결과를 세어보면 아래 표와 같습니다.

A의 주사위	승	무	패
#1, #2	596	196	504
#1, #3	560	176	560
#1, #4	616	184	496
#2, #3	496	184	616
#2, #4	560	176	560
#3, #4	504	196	596

 

A가 승리할 확률이 가장 높아지기 위해선 주사위 #1, #4를 가져가야 합니다.

 

주사위에 쓰인 수의 구성을 담은 2차원 정수 배열 dice가 매개변수로 주어집니다. 이때, 자신이 승리할 확률이 가장 높아지기 위해 A가 골라야 하는 주사위 번호를 오름차순으로 1차원 정수 배열에 담아 return 하도록 solution 함수를 완성해 주세요. 승리할 확률이 가장 높은 주사위 조합이 유일한 경우만 주어집니다.

 

제한사항

• 2 ≤ dice의 길이 = n ≤ 10
• n은 2의 배수입니다.
• dice[i]는 i+1번 주사위에 쓰인 6개의 수를 담고 있습니다.
• dice[i]의 길이 = 6
• 1 ≤ dice[i]의 원소 ≤ 100

입출력 예

dice	result
[[1, 2, 3, 4, 5, 6], [3, 3, 3, 3, 4, 4], [1, 3, 3, 4, 4, 4], [1, 1, 4, 4, 5, 5]]	[1, 4]
[[1, 2, 3, 4, 5, 6], [2, 2, 4, 4, 6, 6]]	[2]
[[40, 41, 42, 43, 44, 45], [43, 43, 42, 42, 41, 41], [1, 1, 80, 80, 80, 80], [70, 70, 1, 1, 70, 70]]	[1, 3]

---

문제 해설

 

문제 자체가 요구하는 알고리즘은, 제귀함수를 사용한 데이터 생성과 이진탐색을 사용한 효율적인 데이터 탐색이다.

 

제귀를 통해 데이터를 제작해서 일정한 SQL로 만든 다음, 정렬하고, 이진탐색을 사용해서 더 효율적인 데이터 탐색과 결과물 도출이 필요하다.

---

첫 번째 시도

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

using namespace std;

int FindToBinary(int number1, const vector<int>& number2)
{
    int answer = 0;
    for (auto& def : number2)
        if (number1 > def) answer++;
        else break;
    return answer;
}

void Make_To_number(const vector<vector<int>>& dice, const vector<int>& diceList, vector<int>& output, int answer = 0, int i = 0)
{
    if (i == diceList.size()) {
        output.push_back(answer);
        return;
    }
    for (auto& def : dice[diceList[i]])
        Make_To_number(dice, diceList, output, answer + def, i + 1);
}

void inertTodice(const vector<vector<int>>& dice, map<vector<int>, vector<int>>& chacklist, vector<int> nowlist , const int& size, int n)
{
    if (n == 0)
    {
        vector<int> make;
        Make_To_number(dice, nowlist, make);
        sort(make.begin(), make.end());
        chacklist[nowlist] = make;
        return;
    }

    for (int i = 0; i < size; i++) {
        vector<int> insert(nowlist);
        bool chack = false;
        for (auto& def : nowlist)
            if (def == i) {
                chack = true; break;
            }

        if (chack == false) {
            insert.push_back(i);
            inertTodice(dice, chacklist, insert, size, n - 1);
        }
    }
}

vector<int> solution(vector<vector<int>> dice) {
    vector<int> answer;
    int size = dice.size();
    map<vector<int>, vector<int>> chacklist;
    inertTodice(dice, chacklist, {}, size, size / 2);

    int chackwin = 0;
    for (auto& numbers : chacklist)
    {
        int nowwin = 0;
        vector<int> ene;
        for (int i = 0; i < dice.size(); i++) {
            bool chack = false;
            for (auto& def : numbers.first)
                if (i == def) {
                    chack = true;
                    break;
                }
            if(chack == false) ene.push_back(i);
        }
        for (auto& number : numbers.second) 
            nowwin += FindToBinary(number, chacklist[ene]);

        if (nowwin > chackwin) {
            answer = numbers.first;
            chackwin = nowwin;
        }
    }
    for (auto& def : answer) def++;
    
    return answer;
}

실패

 

데이터의 이진탐색을 이해하고 적용하였으나, 중복된 데이터를 제거하지 못해서 시간초과가 나타난다.

그리고, 이진탐색을 귀찮아서 최솟값 기준으로 전체배열을 탐색하여 그냥 덧셈으로 했던것도 이유인것 같다.

 

데이터를 정리할 때, 가능한 주사위 경우의 수를 전부 정리한 다음, 해당 주사위 데이터의 승률을 예측해야 한다.

 

승률 예측의 경우, 가능한 모든 주사위 정보 결과를 배열로 저장해놓은 다음, A와 B의 경우의 수를 확인하고, 해당되는 수의 정보결과를 이진탐색법을 사용해서 탐색, 탐색 후에 나타난 결과값을 중첩해서 더하면, 해당 주사위 경우의수에 대한 승리횟수가 나타난다.

 

이 승리횟수를 비교연산하여, 가장 큰 승리횟수를 가진 데이터를 반환하면 끝난다.

---

두 번째 시도

#include <string>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

int FindToBinary(int number1, const vector<int>& number2)
{
    int front = 0;
    int back = number2.size() - 1;

    while (front <= back) {
        int mid = front + (back - front) / 2;

        if (number2[mid] >= number1)
            back = mid - 1;
        else
            front = mid + 1;
    }
    return front;
}

void Make_To_number(const vector<vector<int>>& dice, const vector<int>& diceList, vector<int>& output, int answer = 0, int i = 0)
{
    if (i == diceList.size()) {
        output.push_back(answer);
        return;
    }
    for (auto& def : dice[diceList[i]])
        Make_To_number(dice, diceList, output, answer + def, i + 1);
}

void inertTodice(const vector<vector<int>>& dice, map<vector<int>, vector<int>>& chacklist, vector<int>& nowlist, const int& size, int n)
{
    if (n == 0)
    {
        sort(nowlist.begin(), nowlist.end());
        if (chacklist.count(nowlist) == 0) {
            vector<int> make;
            Make_To_number(dice, nowlist, make);
            sort(make.begin(), make.end());
            chacklist[nowlist] = make;
        }
        return;
    }

    for (int i = 0; i < size; i++) {
        if (find(nowlist.begin(), nowlist.end(), i) == nowlist.end()) {
            vector<int> next(nowlist);
            next.push_back(i);
            inertTodice(dice, chacklist, next, size, n - 1);
        }
    }
}

vector<int> solution(vector<vector<int>> dice) {
    vector<int> answer;
    int size = dice.size();
    map<vector<int>, vector<int>> chacklist;
    
    vector<int> def;
    inertTodice(dice, chacklist, def, size, size / 2);
    
    vector<vector<int>> chackVector;
    chackVector.reserve(chacklist.size() * 36);
    
    for (auto& def : chacklist) chackVector.push_back(def.first);

    int chackwin = 0;
    for (int number = 0; number < chackVector.size(); number++)
    {
        int nowwin = 0;
        vector<int>& numbers = chackVector[number];
        vector<int>& ene = chackVector[chackVector.size() - 1 - number];

        for (auto& number : chacklist[numbers])
            nowwin += FindToBinary(number, chacklist[ene]);

        if (nowwin > chackwin) {
            answer = numbers;
            chackwin = nowwin;
        }
    }

    for (auto& def : answer) def++;
    return answer;
}

성공

중복된 데이터를 걸러서 생성되지 않도록 정리했다. [1, 2]와 [2, 1]은 같은 데이터가 도출됨으로 필요가 없다.