백준 9742 - 순열

문제링크

• 백준 9742

문제 접근

• 집합의 순열을 구하는 함수로 algorithm 헤더파일에 있는 next_permutation 함수를 선택했다.
• k번째 순열을 찾으려면 위 함수를 k번 호출하면 된다.
• 순열을 만드는 경우의 수는 n개의 원소에 대해서 n! 이므로 해당 경우의 수보다 큰 값이 들어오는지 확인한다.

의사코드(pseudo-code)

#define function
- int factorial(const int& a)
	- val = 1
	- for i=2 to a: val = val * i
	- return val

#main
- while true:
	- if cin.eof() is true: break // 파일의 끝에 도달하면 탈출
	- cin >> str >> n
	- len = str.length()
	- limit = factorial(len)
	- if n > limit : "No permutation" 출력, continue
	- for i=0 to n-1:
		- next_permutation(str.begin(). str.end())
	- 출력 형식에 맞춰서 결과 출력

소스코드 및 분석

전체 코드

#include <iostream>
#include <string>
#include <algorithm>

int factorial(const int& a) {
	int val = 1;
	for (int i = 2; i <= a; i++) val *= i;
	return val;
}

int main()
{
	while (true) {
		std::string str; int n;
		std::cin >> str >> n;
		if (std::cin.eof()) break;
		int len = str.length();
		int limit = factorial(len);
		std::cout << str << " " << n << " = ";
		if (n > limit) {
			std::cout << "No permutation\n";
			continue;
		}
		for (int i = 1; i < n; i++)
			std::next_permutation(str.begin(), str.end());
		std::cout << str << "\n";
	}
}

다른 풀이

• 재귀호출로 순열을 구하는 함수를 구현하였다.
• 순열을 만드는 과정은 다음과 같다.
  1. n개의 수 중 1개를 선택한다.
  2. n-1개의 수 중 1개를 선택한다.
  3. n-2개의 수 중 1개를 선택한다.
  4. …
  5. …

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

void make_permutation(string& str, string& nstr, vector<bool>& visited, int& idx, int& cnt, bool& flag, int& len) {
	// 기저사례 nstr.size()==str.size()
	if (nstr.size() == len) {
		cnt++;
		if (idx == cnt) {
			flag = true;
			cout << nstr << endl;
		}
		return;
	}

	for (int i = 0; i < len; i++) {
		if (visited[i] == true) continue;
		visited[i] = true;
		nstr.push_back(str[i]);
		make_permutation(str, nstr, visited, idx, cnt, flag, len);
		nstr.pop_back();
		visited[i] = false;
	}
	return;
}

int main()
{
	while (true) {
		string str;
		int idx;
		cin >> str >> idx;
		if (cin.eof()) break;

		int len = str.length();
		string nstr;
		vector<bool> visited(len, false);
		int cnt = 0;
		bool flag = false;

		cout << str << " " << idx << " = ";
		make_permutation(str, nstr, visited, idx, cnt, flag, len);
		if (flag == false) cout << "No permutation" << endl;
	}
}