백준 9742번 [순열](C++) -yes6686- 티스토리

백준 문제 풀이: 9742번 [순열]

---

문제 링크: https://www.acmicpc.net/problem/9742

문제 설명:

주어진 문자열의 모든 순열을 사전식으로 나열한 뒤, 특정 순열 번호에 해당하는 값을 출력하는 문제입니다. 만약 순열 번호가 가능한 범위를 벗어나면 "No permutation"을 출력해야 합니다.

---

문제 해결 코드

#include <iostream>
#include <string>
#include <cstring> // memset 사용
using namespace std;

string str[3628801]; // 순열을 저장할 배열 (최대 10! = 3628800)
int visited[11];     // 방문 여부를 저장할 배열
string st;           // 입력 문자열

int cnt = 1;         // 순열 번호

// 깊이 우선 탐색으로 순열 생성
void dfs(int d, int n, string s) {
    if (d > n) {
        str[cnt] = s; // 순열 저장
        cnt++;
        return;
    }

    for (int i = 0; i < n; i++) {
        if (visited[i] == 0) { // 아직 사용하지 않은 문자라면
            visited[i] = 1;   // 방문 표시
            dfs(d + 1, n, s + st[i]); // 다음 단계로 이동
            visited[i] = 0;   // 방문 해제
        }
    }
}

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

    int n;
    while (cin >> st >> n) {
        cnt = 1; // 순열 카운터 초기화
        dfs(1, st.size(), ""); // DFS로 순열 생성

        cout << st << ' ' << n << " = ";
        if (cnt <= n) {
            cout << "No permutation" << '\n'; // 범위를 벗어난 경우
        } else {
            cout << str[n] << '\n'; // n번째 순열 출력
        }
        memset(visited, 0, sizeof(visited)); // 방문 배열 초기화
    }
}

---

코드 설명

위 코드는 입력 문자열의 모든 순열을 DFS를 통해 생성하며, 주어진 순열 번호에 해당하는 값을 출력합니다. 주요 로직은 다음과 같습니다:

1. DFS로 순열 생성: 각 문자를 하나씩 추가하며 모든 순열을 탐색하고 저장합니다.
2. 순열 번호 검증: 주어진 순열 번호가 가능한 순열 개수 이내인지 확인합니다.
3. 초기화: 새로운 입력에 대해 방문 여부와 순열 배열을 초기화하여 재사용합니다.

제한사항: 최대 입력 문자열의 길이는 10이며, 이는 최대 10! (3628800개)의 순열을 생성합니다.

---

결과

위 코드를 통해 문제를 해결할 수 있으며, 입력 문자열과 원하는 순열 번호에 대해 정확한 결과를 반환합니다. 최적화를 통해 성능을 개선하거나 다른 접근 방식을 제안하고 싶다면 댓글로 공유 부탁드립니다!