백준 9742번 순열 [C++]

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

 

 

#문제 간단 정리

dfs 등 완전탐색으로 

순열을 탐색해 

해당 순번의 순열을 출력하는 문제

 

 

 

#문제 해결 방법

우선 eof 를 확인하는 입출력에 주의 

https://dfdfg42.tistory.com/entry/%EB%B0%B1%EC%A4%80-C-eof-%EC%B2%98%EB%A6%AC-%EB%B0%A9%EB%B2%95

백준 C++ eof 처리 방법

 

 

나는 dfs 로 

모든 문자열을 계속해서 만들었고

문자열을 하나 만들때마다 찾은 문자열의수 seq 를 증가시켜주고

seq로 그 문자열 몇번째 순서인지 기억하여

우리가 찾는순번의 문자열이면 ans로 저장을 했다.

 

만들어진 문자열의 총 개수가 찾는 인덱스 보다 클 때만 정답이 있으니

이때만 ans 출력해주면 된다.

 

 

그리고 dfs의 인덱스 처리에 주의해주고 

 

처음에는 모든 문자열을 저장하려고 했는데 

메모리 초과가 나서

그냥 그 순번의 문자열만 저장하도록 바꿨다.

 

#전체 코드

 

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

bool visited[10];
string s;
int totalLength;
int findSeq;
int seq;
string ans;


void dfs(int idx,string make) {
    if (idx == totalLength) {
        seq += 1;
        if (seq == findSeq) {
            ans = make;
        }

        return;
    }

    for (int i = 0; i <= totalLength; i++) {
        if (!visited[i]) {
            visited[i] = true;
            make += s[i];
            dfs(idx + 1, make);
            make.pop_back();
            visited[i] = false;
        }
    }

}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    while (1) {

        cin >> s >> findSeq;
        totalLength = s.length()-1;

        seq = 0;
        
        memset(visited, false, sizeof(visited));

        if (cin.eof()) {
            break;
        }


        dfs(-1, "");

        if (seq >= findSeq) {
            cout << s << " " << findSeq << " = " << ans << '\n';
        }
        else {
            cout << s << " " << findSeq << " = No permutation"  << '\n';
        }

    }

    
    return 0;
}