[백준] 순열장난

✔️ 문제

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

✔️ 문제 요약과 이해

• 1부터 N까지의 수로 이루어진 순열이 있다. 근데 해당 순열의 공백을 모두 지워버렸다.
• 순열을 복구해서 출력한다. 복구한 수열의 경우가 여러 가지일 경우, 그 중 하나를 출력한다.
• 순열은 최소 1개 최대 50개의 수로 이루어져 있다. (N의 최대 크기는 50이다.)

✔️ 풀이

• 1부터 N까지의 수로 이루어진 순열이란 다음과 같다.
  • N이 4일 경우 : 1, 2, 3, 4 또는 4, 2, 1, 3 또는 3, 1, 4, 2 …
  • N이 8일 경우 : 1, 2, 3, 4, 5 ,6 ,7, 8 또는 8, 3, 4, 1, 7, 5, 2, 6 …
• 공백이 제거된 순열을 문자열 형태로 입력 받고, 문자열을 1개 단위, 2개 단위로 잘라보며 순열을 찾아본다.
• 순열의 최대값 N을 구해서 N이하의 숫자만 순열에 추가해야한다.
• 순열의 최대값 N은 입력으로 주어지는 공백이 지워진 순열을 통해 구할 수 있다.

👨🏻‍💻 소스 코드

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

string str;
vector<int> ret;
int maxNum;
bool check[50], flag;

void dfs(int index) {

	if (index == str.size()) {
		for (int tmp : ret)
			cout << tmp << " ";
		exit(0);
	}

	int num = stoi(str.substr(index, 1));

	if (num <= maxNum) { // 1개씩 자르는 경우(순열의 포함된 최대값보다 작아야 한다.)
		if (!check[num]) { // 이미 순열에 포함된 수인지 체크한다. 
			check[num] = true;
			ret.push_back(num);
			dfs(index + 1); // 1개를 잘랐으므로 인덱스를 하나 증가시킨다.
			ret.pop_back();
			check[num] = false;
		}
	}
	
	num = stoi(str.substr(index, 2));

	if (num <= maxNum){ // 2개씩 자르는 경우 
		if (!check[num]) {
			check[num] = true;
			ret.push_back(num);
			dfs(index + 2); // 2개를 잘랐으므로 인덱스를 두 개 증가시킨다.
			ret.pop_back();
			check[num] = false;
		}
	}

}

int main() {
	cin >> str;

	maxNum = (str.size() - 9) / 2 + 9; // 순열의 최대값을 구한다. 
	
	dfs(0);
	return 0;
}

✔️ 문제 회고

• 문제를 온전히 이해하는데, 시간이 좀 걸렸다.
• 재귀를 통해 모든 경우의 수를 찾는 백트래킹에 더 익숙해져야겠다.