[BOJ/백준 15663][C++] N과 M (9)

문제

https://www.acmicpc.net/problem/15663

백준 15663

 

문제 내용

입력받은 N개의 자연수 중에 M개를 골라 수열을 만들어 출력하면 된다.

이때 수열을 사전순으로 증가하는 순서대로 출력해야 하며, 수열이 중복되면 안 된다.

하지만, 입력으로 주어지는 원소 N개 사이에는 중복이 있을 수 있다.

 

문제 풀이

N과 M (5)과 다르게 N과 M (9)는 입력받은 원소가 중복이 존재할 수 있다.

따라서 n=3, m=2, [10,10,9]를 입력받았을 때 아래와 같이 출력되어야 한다.

9 10
10 9
10 10

[9,10]이나 [10,9]가 2번 출력되면 절대 안 된다.

 

하지만 이 문제에서 set을 사용하여 중복을 제거하면 안 된다. 

set은 기본적으로 사전순 정렬이 되기 때문에, 위의 예시의 경우 아래와 같이 출력되기 때문이다.

10 9
10 10
9 10

 

또한 cnt==m일 때 바로 출력하는 대신 resultArr에 넣고, main()에서 나중에 unique를 써서 중복을 제거하는 것 또한 안 된다. unique를 사용하려면 먼저 정렬을 해야 하기 때문이다. (마찬가지로 사전순 정렬이다)

 

그래서 나는 같은 step에서 같은 원소가 여러 번 사용되지 않게, 이전에 result[cnt]에 넣은 값을 기억하도록 했다.

 

코드

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int n, m;
vector<int> arr;
vector<int> used(8, 0);
vector<int> result(8, 0);

void back(int cnt) {
    if (cnt == m) {
        for (int i = 0; i < m; i++) {
            cout << result[i] << ' ';
        }
        cout << '\n';
        return;
    }

    int check_duplicate = -1;
    for (int i = 0; i < n; i++) {
        if (!used[i] && check_duplicate != arr[i]) {
            check_duplicate = arr[i];
            used[i] = true;
            result[cnt] = arr[i];
            back(cnt + 1);
            used[i] = false;
        }
    }
}

int main() {
    cin >> n >> m;
    arr.assign(n, 0);

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    sort(arr.begin(), arr.end());

    back(0);
}

 

문제 코드 설명

check_duplicate라는 변수를 통해, 해당 스텝에 같은 수가 여러 번 들어가지 않게 했다.

arr배열을 main에서 백트래킹 전에 정렬을 해두었기 때문에, 중복되는 원소들은 이미 한군데 뭉쳐져 있게 된다. 그래서 check_duplicate 값과 arr[i] 같은 경우, 바로 이전 원소(arr[i-1])와 현재 값(arr[i])이 중복이었다는 것을 알 수 있게 된다.