[백준] 15663_N과 M (9) C++

19 Jun 2023 in Study on Coding Test

백트래킹과 Set을 활용해보는 문제

정답제출코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

int N, M;
vector<pair<int, int>> arr;
vector<int> arrOutput;
set<vector<int>> already;

bool IsAlready(vector<int> a)
{
    if (already.find(a) == already.end())
    {
        already.insert(a);
        return false;
    }
    else
        return true;
}

int InputSearch(int a)
{
    for (size_t i = 0; i < arr.size(); ++i)
    {
        if (arr[i].first == a)
            return i;
    }
    return -1;
}

void backtrack(int count)
{
    if (count == M)
    {
        if (!IsAlready(arrOutput))
        {
            for (size_t i = 0; i < arrOutput.size(); ++i)
                cout << arrOutput[i] << ' ';
            cout << '\n';
        }
        return;
    }

    for (size_t i = 0; i < arr.size(); ++i)
    {
        if (arr[i].second != 0)
        {
            arr[i].second--;
            arrOutput.push_back(arr[i].first);
            backtrack(count+1);
            arrOutput.pop_back();
            arr[i].second++;
        }
    }
}


int main()
{
    cin >> N >> M;

    for (int i = 0 ; i < N; ++i)
    {
        int _input;
        cin >> _input;

        int Index = InputSearch(_input);

        if (Index != -1)
            arr[Index].second++;
        else
            arr.push_back({_input, 1});
    }

    sort(arr.begin(), arr.end());

    backtrack(0);

    return 0;
}

백트래킹을 통해서 조건을 만족하는 모든 경우의 수를 구하는 문제이다.

이번엔 입력 값에 중복된 숫자가 들어가지만,

출력 결과에는 중복이 없다.

예를 들어

// input
4 2
9 7 9 1

// output
1 7
1 9
7 1
7 9
9 1
9 7
9 9

위에서 9가 2개라면 1 9가 2번, 7 9가 2번 나올 수 있는 형태가 된다.

하지만 위의 테스트 케이스대로라면 중복된 결과가 또 나와서는 안된다.

이를 어떻게 구현할까 고민했는데 Set을 활용하기로 하였다.

set<vector<int>> already;

bool IsAlready(vector<int> a)
{
    if (already.find(a) == already.end())
    {
        already.insert(a);
        return false;
    }
    else
        return true;
}

...

if (count == M)
{
    if (!IsAlready(arrOutput))
    {
        for (size_t i = 0; i < arrOutput.size(); ++i)
            cout << arrOutput[i] << ' ';
        cout << '\n';
    }
    return;
}

벡터 배열을 출력할 때, 벡터가 set에 없고 처음 나오는 거라면

set에다가 해당 벡터를 담아준다. 그렇게해서 다시 중복된 결과가 출력되는 것을 방지해준다.

그리고 아래 테스트 케이스와 같이

// input
4 4
1 1 1 1

// output
1 1 1 1

입력에서는 같은 숫자가 들어갈 수 있게 구현해야했다.

이는 입력 벡터를 int2개의 쌍을 받게 해서 해결하였다.

첫번째에는 입력 값을, 두번째에는 그 값이 몇개에 있는지를 저장한다.

int InputSearch(int a)
{
    for (size_t i = 0; i < arr.size(); ++i)
    {
        if (arr[i].first == a)
            return i;
    }
    return -1;
}

...

for (int i = 0 ; i < N; ++i)
{
    int _input;
    cin >> _input;

    int Index = InputSearch(_input);

    if (Index != -1)
        arr[Index].second++;
    else
        arr.push_back({_input, 1});
}

InputSearch 함수에서는 값이 없다면 -1을,

있다면 몇번 인덱스에 있는지를 반환하게 구현하였다.

이렇게 해서 코드를 완성하였다.