[프로그래머스] 주사위 고르기 (C++)

공부 스파이럴·2024년 5월 6일

프로그래머스

목록 보기

9/18

문제

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

아이디어1

pair를 이용해서 pair<중복된 주사위 눈, 개수>로 변환하기

vector<vector<pair<int, int>>> dice_duple;
for (auto iter_d = dice.begin(); iter_d != dice.end(); ++iter_d)
{
    vector<pair<int, int>> duple;

    auto iter_n = iter_d->begin();
    duple.emplace_back(pair<int, int>(*iter_n, 1));
    iter_n++;

    for (; iter_n != iter_d->end(); ++iter_n)
    {
        if (*iter_n == duple.back().first)
            duple.back().second++;
        else
            duple.emplace_back(pair<int, int>(*iter_n, 1));

    }
    dice_duple.emplace_back(duple);
}

#1과 #2의 경우 $6\times6=36$ 이 아닌 $6\times2=12$ 가 가능

아이디어2-1

combination을 구현해서 가능한 주사위 조합 구하기

[0 1 2] 과 [0 2 1] 같은 중복은 필요없기 때문에 permutation을 이용해서 없애도록 하자

1100이란 비트마스크와 prev_permutation를 이용하면
1100 / 1010 / 1001 / 0110 / 0101 / 0011
이 때, 1을 A의 주사위, 0을 B의 주사위라고 생각하면 됨

아이디어2-2

A의 승은 B의 패, B의 승은 A의 패

즉, combination의 절반은 필요가 없다

방법은 A는 항상 1번 주사위를 가지고 있다고 가정

절반의 경우의 수를 줄일 수 있음

#1, #2를 구하면 #3, #4의 경우를 구할 필요가 없다

void combination(int N, int K, const vector<vector<pair<int, int>>>& dice, int& max, vector<int>& answer)
{
    vector<bool> bitmask(K - 1, true);
    bitmask.resize(N - 1, false);
    
    do {
        vector<int> numbers_A = { 0 };
        vector<int> numbers_B;
        for (int i = 0; i < N - 1; ++i)
        {
            if (bitmask[i] == true)
                numbers_A.emplace_back(i + 1);
            else
                numbers_B.emplace_back(i + 1);
        }
        calculate(numbers_A, numbers_B, dice, max, answer);
    } while (prev_permutation(bitmask.begin(), bitmask.end()));
}

N : 전체 개수, K : 선택할 수의 개수
1번 주사위는 A가 가지고 있기 때문에 N-1, K-1에 대해서 진행

아이디어3

unordered_map을 이용해서 <key : 합, value : 개수>로 저장

// key : 합, value : 수
unordered_map<int, int> sum_A;
unordered_map<int, int> sum_B;

// 첫 주사위 6개 넣어 초기화
auto iter_A = numbers_A.begin();
for (auto iter = dice[*iter_A].begin(); iter != dice[*iter_A].end(); ++iter)
{
    sum_A.emplace((*iter).first, (*iter).second);
}
iter_A++;

// 다음 주사위들 합하기
for (; iter_A != numbers_A.end(); ++iter_A)
{
    unordered_map<int, int> tempSum;
    for (auto& ele : sum_A)
    {
        for (auto iter = dice[*iter_A].begin(); iter != dice[*iter_A].end(); ++iter)
        {
            // operator[]는 key가 없다면 생성, int의 경우 0초기화 보장
            tempSum[ele.first + (*iter).first] += ele.second * (*iter).second;
        }  
    }

    swap(sum_A, tempSum);
}

auto iter_B = numbers_B.begin();
for (auto iter = dice[*iter_B].begin(); iter != dice[*iter_B].end(); ++iter)
{
    sum_B.emplace((*iter).first, (*iter).second);
}    
iter_B++;

for (; iter_B != numbers_B.end(); ++iter_B)
{
    unordered_map<int, int> tempSum;
    for (auto& ele : sum_B)
    {
        for (auto iter = dice[*iter_B].begin(); iter != dice[*iter_B].end(); ++iter)
        {
            tempSum[ele.first + (*iter).first] += ele.second * (*iter).second;
        }  
    }

    swap(sum_B, tempSum);
}

unordered_map의 operator[]의 경우 key가 있으면 value를 찾아주지만 없다면 원소를 생성해준다
- 이 때, value가 int면 0으로 초기화 해주는 걸 보장해준다고 함
각각의 개수를 곱해서 더하면 중복된 주사위의 눈을 새로 더할 필요가 없어짐

int win = 0;
int lose = 0;

for (auto A : sum_A)
{
    for (auto B : sum_B)
    {
        if (A.first > B.first)
            win += A.second * B.second;
        else if (A.first < B.first)
            lose += A.second * B.second;
    }
}

if (max < win)
{
    answer = numbers_A;
    max = win;
}
if (max < lose)
{
    answer = numbers_B;
    max = lose;
}