개요

백준: 10597(순열 장난)

• 입력
  첫 줄에 공백이 사라진 kriii의 수열이 주어진다.

  kriii의 순열은 최소 1개 최대 50개의 수로 이루어져 있다.

• 출력
  복구된 수열을 출력한다. 공백을 잊으면 안 된다.

  복구한 수열의 경우가 여러 가지 일 경우, 그 중 하나를 출력한다.

접근 방식

1. 입력숫자열을 string으로 가져온 후, 백트래킹 방식을 이용해
   한 글자 or 두 글자씩 끊어서 이미 방문한 숫자인지 체크하고 수열을 만들었다.

2. 백트래킹 함수의 인자로는 답을 넣을 벡터 (값복사가 일어나지 않도록 참조자를 사용하였다.) 와 이번에 파싱할 부분이 어딘지 알려주는
   int형 변수를 사용하였다.

//끊어서 분리한 숫자를 저장할 벡터, 어디까지 끊었는지 offset
void Backtracking(vector<int>& v,int offset) 

3. 만약 끝까지 파싱을 하여 벡터에 다 넣었다면
   방문배열을 다 체크해서 다 방문했다면 답으로 출력하고
   백트래킹 빠져나오게 하는 bool형 변수 didPrint를 true로 넣어준다.

	//끝까지 분리했다면 
	if (offset == inputArr.length()) {
		//만약 1부터 제일큰 숫자까지 비어있는 값이있다면 return;
		for (int i = 1; i <= maxNum; i++) {
			if (!visited[i]) return;
		}
		//다 차있다면 다 출력
		for (auto iter = v.begin(); iter != v.end(); ++iter) {
			cout << *iter << " ";
		}
		//출력시 didPrinted를 true로 
		didPrinted = true;
		return;
	}

4. 그 후로 offset위치의 한자리 숫자를 파싱해오는데,
   해당 값이 0이라면 return해야한다. (이 부분을 놓쳐서 검색했었다 ㅜ)

	//offset부터 숫자하나 따오기
	int num = inputArr[offset] - '0';

	//0인 수는 없으므로 다시 전단계로 돌아가서 두개를 넣어야함
	if (num == 0) return;

5. 그 후 지금까지 넣었던 숫자중 제일큰 숫자를 갱신해준 후,
   백트래킹 함수 실행후, 돌아왔을때 변경한값들 초기화해준다.

   여기서 주의할 점은 한자리수를 방문한적있다고 return해버리면
   밑에 두자리수처리하는 부분을 도달하지못하므로
   한자리수 방문안했을때를 체크하고 파싱하고 백트래킹하게 해줬다.

//숫자가 방문한적있따고  return 처리시 숫자 두개 따오는 과정을 스킵함 
	//해당 숫자가 방문한적 없는 숫자라면 
	if (!visited[num] && num!=0) 
	{
		//백트래킹함수에서 돌아왔을 때를 대비해 maxnum갱신하기전값 저장
		int tmpMaxNum = maxNum;
		//제일 큰수 저장
		maxNum = maxNum > num ? maxNum : num;
		//방문 처리
		visited[num] = true;
		//v에 넣어주기
		v.push_back(num);
		//백트래킹함수 다음 단계 실행
		Backtracking(v, offset + 1);
		//끝내고 돌아왔을때 출력한 상태라면 return
		if (didPrinted) return;
		//제일 큰 숫자 다시 되돌리기
		maxNum = tmpMaxNum;
		//num방문 취소 
		visited[num] = false;
		//들어갔던 num값 뺌
		v.pop_back();
	}

6. 그다음 이제 두글자를 파싱해야하는데 문자열남은 원소가 두글자보다 적을때 return해준다

	if (offset == inputArr.length() - 1) return;

7. 두 글자를 파싱해서 숫자로 변환해주고 두자리수가 50 초과하면
   return해주고(이 부분도 놓쳐서 또 한번 인터넷을 찾아 헤맸다 ㅜ)
   두자리수도 방문했다면 바로 return해준다.

	//두글자 따기
	int twoDigitNum = (inputArr[offset++] - '0') * 10 + inputArr[offset] - '0';

	//두자릿수가 50초과하거나한자리수와 두자리수 둘다 방문했다면 return해줌
	if (twoDigitNum>50 || visited[twoDigitNum]) return;

8. 나머지 부분은 한자리수일때와 똑같이 백트래킹 함수 실행후
   변경값들 초기화다.

	int tmpMaxNum = maxNum;	
	//제일 큰수 저장
	maxNum = maxNum > twoDigitNum ? maxNum : twoDigitNum;
	//방문 처리
	visited[twoDigitNum] = true;
	//v에 넣어주기
	v.push_back(twoDigitNum);
	//백트래킹함수 다음 단계 실행
	Backtracking(v, offset + 1);
	//끝내고 돌아왔을때 출력한 상태라면 return
	if (didPrinted) return;
	//제일 큰 숫자 다시 되돌리기
	maxNum = tmpMaxNum;
	//num방문 취소 
	visited[twoDigitNum] = false;
	//들어갔던 num값 뺌
	v.pop_back();
}

전체 코드

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

bool visited[51];
string inputArr="";
int maxNum = 0;
bool didPrinted = false;
void Input() {
	cin >> inputArr;
}

//끊어서 분리한 숫자를 저장할 벡터, 어디까지 끊었는지 offset
void Backtracking(vector<int>& v,int offset) {
	//끝까지 분리했다면 
	if (offset == inputArr.length()) {
		//만약 1부터 제일큰 숫자까지 비어있는 값이있다면 return;
		for (int i = 1; i <= maxNum; i++) {
			if (!visited[i]) return;
		}
		//다 차있다면 다 출력
		for (auto iter = v.begin(); iter != v.end(); ++iter) {
			cout << *iter << " ";
		}
		//출력시 didPrinted를 true로 
		didPrinted = true;
		return;
	}
	//offset부터 숫자하나 따오기
	int num = inputArr[offset] - '0';

	//0인 수는 없으므로 다시 전단계로 돌아가서 두개를 넣어야함
	if (num == 0) return;

	//숫자가 방문한적있따고  return 처리시 숫자 두개 따오는 과정을 스킵함 
	//해당 숫자가 방문한적 없는 숫자라면 
	if (!visited[num] && num!=0) 
	{
		//백트래킹함수에서 돌아왔을 때를 대비해 maxnum갱신하기전값 저장
		int tmpMaxNum = maxNum;
		//제일 큰수 저장
		maxNum = maxNum > num ? maxNum : num;
		//방문 처리
		visited[num] = true;
		//v에 넣어주기
		v.push_back(num);
		//백트래킹함수 다음 단계 실행
		Backtracking(v, offset + 1);
		//끝내고 돌아왔을때 출력한 상태라면 return
		if (didPrinted) return;
		//제일 큰 숫자 다시 되돌리기
		maxNum = tmpMaxNum;
		//num방문 취소 
		visited[num] = false;
		//들어갔던 num값 뺌
		v.pop_back();
	}
	if (offset == inputArr.length() - 1) return;
	//두글자 따기
	int twoDigitNum = (inputArr[offset++] - '0') * 10 + inputArr[offset] - '0';

	//두자릿수가 50초과하거나한자리수와 두자리수 둘다 방문했다면 return해줌
	if (twoDigitNum>50 || visited[twoDigitNum]) return;

	int tmpMaxNum = maxNum;	
	//제일 큰수 저장
	maxNum = maxNum > twoDigitNum ? maxNum : twoDigitNum;
	//방문 처리
	visited[twoDigitNum] = true;
	//v에 넣어주기
	v.push_back(twoDigitNum);
	//백트래킹함수 다음 단계 실행
	Backtracking(v, offset + 1);
	//끝내고 돌아왔을때 출력한 상태라면 return
	if (didPrinted) return;
	//제일 큰 숫자 다시 되돌리기
	maxNum = tmpMaxNum;
	//num방문 취소 
	visited[twoDigitNum] = false;
	//들어갔던 num값 뺌
	v.pop_back();
}

void Solution() {
	vector<int> v;
	Backtracking(v,0);
}

int main() {
	Input();
	Solution();
}

문풀후생

반례찾은 출처들이다.
https://www.acmicpc.net/board/view/88098
->
67891054321

ans : 6 7 8 9 10 5 4 3 2 1

https://www.acmicpc.net/board/view/31913
->
155987643211011121314

답은

15 5 9 8 7 6 4 3 2 1 10 11 12 13 14