BOJ 15663 N과 M (9)

문제

중복된 숫자가 포함된 $N$개의 수에서 $M$개를 고른 수열을 중복 없이 사전 순으로 출력하기.

복잡도 분석

시간 복잡도: $O(N \cdot N!)$. $N=8$일 때 $8 \times 40,320$은 약 32만 회 연산으로 1초 제한 내 가능

공간 복잡도: $O(N)$. 재귀 깊이가 최대 8이며, 전역 벡터와 방문 배열 정도의 메모리만 사용합니다.

접근법

입력받은거 정렬해서 사전순 출력 되도록 하고

인덱스 중복 방지로 visited 배열 쓴다

이것만 하면 똑같은 숫자가 여러개 있을 경우 같은 수열이 나오게 되는데, 마지막 for 문에서 사용된 변수(last_value) 사용해서 같은 숫자가 여러번 나오지 않도록 한다. 정렬된 상태라서 가능

풀이

#include<bits/stdc++.h>
#include<iostream>
using namespace std;

int N,M;
vector<int> v{};
vector<int> res{};
vector<bool> visited{};

void dfs(){
    if (size(res)==M){
        for(const auto &e:res){
            cout << e << " ";
        }
        cout << "\n";
        return;
    }
    int last=-1;
    for(int i=0;i<N;i++){
        if(!visited[i] && v[i]!=last){
            visited[i] = true;
            res.push_back(v[i]);
            last = v[i];
            dfs();
            visited[i]=false;
            res.pop_back();
        }
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin>>N>>M;
    for(int i=0;i<N;i++){
        int x; cin >>x;
        v.push_back(x);
    }

    sort(v.begin(),v.end());
    for(int i=0;i<size(v);i++){
        visited.push_back(false);
    }

    dfs();
}

이전 백트래킹 코드가 못생겨서 적어둠

배열이랑 변수들 전역으로 선언하면 깔끔하다. 함수 인자로 depth 사용하거나 vector는 안에서 몇개 push했는지 알수 있으니까 인자가 필요 없게 됨.