백준 9742 순열 C++

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

9742번: 순열

문제

집합의 순열이란 집합의 서로 다른 원소를 모두 사용해 만들 수 있는 순서이다. 예를 들어, {2,3,5}의 순열은 다음과 같다.

1. 2 3 5
2. 2 5 3
3. 3 2 5
4. 3 5 2
5. 5 2 3
6. 5 3 2

각각의 순열은 숫자로 나타낼 수 있다. 위의 순열은 사전순으로 쓰여져 있으며, 등장하는 순서를 이용해 나타낸다. 즉, 3 5 2는 위치 4에 있고, 5 3 2는 마지막 위치인 6에 있다.

{b,e,i,n}으로 만들 수 있는 순열은 다음과 같다.

1. b e i n
2. b e n i
3. b i e n
4. b i n e
5. b n e i
6. b n i e
7. e b i n
8. e b n i
9. e i b n
10. e i n b
11. e n b i 
12. e n i b
13. i b e n
14. i b n e
15. i e b n
16. i e n b
17. i n b e
18. i n e b
19. n b e i
20. n b i e
21. n e b i
22. n e i b
23. n i b e
24. n i e b

서로 다른 숫자와 문자로 이루어진 집합과 위치가 주어졌을 때, 그 집합의 순열 중 주어진 위치의 순열을 구하는 프로그램을 작성하시오.

---

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 문자열은 서로 다른 숫자와 알파벳으로 이루어져 있으며, 길이는 최대 10이다. 또한, 사전순 순서대로 주어진다. 문자열 다음에는 찾아야 하는 위치가 주어지며, 이 값은 3,628,800보다 작거나 같은 자연수이다.

---

출력

각각의 테스트 케이스마다, 입력으로 주어진 위치에 해당하는 순열을 공백없이 출력한다. 만약, 해당하는 순열이 없는 경우에는 "No permutation"을 출력한다.

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main(void){
    while(1){
        
        string str;
        cin >> str;
        int n;
        cin >> n;
       
        if(cin.eof()){
            break;
        }
        
        vector<char> v;
        for(int i = 0;i<str.size();i++){
            v.push_back(str[i]);
        }
        int index = 1;
        sort(v.begin(),v.end());
        bool valid = false;
 
        do{
            if(index == n){
 
                cout << str << ' ' << n << " = ";
               for(int i = 0;i<str.size();i++){
               cout << v[i];
               valid = true;
           }
                cout << '\n';
            }
 
            index++;
 
 
        }while(next_permutation(v.begin(),v.end()));
          if(valid == false){
              cout << str << ' ' << n << " = ";
                cout << "No permutation" << '\n';
            }
    }
}