#9742 : 순열

풀이방법

사용된 것:
백트래킹

2022.05.10
백트래킹 문제이다.
아래의 정답 코드는 가지치기 없이 모든 경우의 수를 다 검사하도록 하였고
이렇게 해도 시간초과가 나지 않기 때문에
브루트포스 알고리즘 문제라고도 할 수 있다.

가능한 모든 순열을 만들면서, 새 순열이 만들어질 때마다 하나씩 세어준다.
세다가 그 숫자가 문제에서 주어진 번호(N)에 도달하면 그 번호의 순열을 출력 문자열에 추가하면 된다.

주어지는 글자들이 사전순으로 주어지므로, 입력 문자열의 앞에 있는 글자부터 하나씩 순서대로 순열에 추가하는 식으로 순열을 만들면 된다. 그럼 결과물인 순열들도 자연스럽게 사전순으로 앞에 있는 것부터 순서대로 도출된다.

"No permutation"을 출력해야 하는 유일한 경우는 바로
문제에서 주어진 번호(N)가
가능한 모든 순열의 개수보다 클 때이다.
그러므로 이를 꼭 점검해주도록 한다.

백트래킹은 막상 해보면 그리 어렵지 않은데 익숙하지 않아 매번 헤매게 된다. 백트래킹 문제 특훈을 좀 해야겠다.

코드

Java(2022.05.10)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	static StringBuilder sb;	//정답 문자열들을 저장할 스트링빌더
	static char[] inputStr;		//입력값으로 주어진 문자열
	static char[] temp;	//지금 만들어지고 있는 순열
	static boolean[] visited;	//temp에 각 글자가 포함된 상태인지 기록(포함됐으면 true)
	static int len;	//완전한 순열의 길이
	static int n;	//찾아야 하는 순열의 번호
	static int curn;	//이번에 만든 순열의 번호

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
		sb = new StringBuilder();
		
		//문제 풀기
		String input = null;
		while((input = br.readLine()) != null) {
			//입력값 읽어오기
			StringTokenizer st = new StringTokenizer(input);
			inputStr = st.nextToken().toCharArray();
			n = Integer.parseInt(st.nextToken());
			
			sb.append(input + " = ");
			
			//필요한 변수및 배열들을 선언하기
			len = inputStr.length;
			curn = 0;
			visited = new boolean[len];
			temp = new char[len];
			
			//정답 찾기
			backtrack(0);
			
			//해당하는 순열이 없는 경우(가능한 모든 순열의 개수보다 n이 더 큰 경우)
			if(n>curn) sb.append("No permutation" + System.lineSeparator());

		}
		
		//정답 출력
		System.out.print(sb);

	}
	
	//정답을 찾는 백트래킹함수
	static void backtrack(int curlen) {
		//curlen은 지금까지 만든 순열의 길이임. curlen이 len과 같아지면 완전한 순열 하나가 완성된 것임.
		
		//완전한 순열 하나가 만들어진 경우
		if(curlen == len) {
			curn++;
			if(curn == n) {
				//이번 순열이 정답 순열인 경우 정답문자열에 순열을 추가
				for(char c : temp) sb.append(c);
				sb.append(System.lineSeparator());
			}
			return;
		}
		
		//아직 완전한 순열이 만들어지지 않아서 더 글자를 붙여야 하는 경우
		for(int i = 0; i<len; i++) {	//주어진 모든 글자에 대하여 오름차순으로
			if(visited[i]) continue;	//이미 순열에 포함된 글자라면 넘어가기
			temp[curlen] = inputStr[i];	//포함되지 않은 글자면 순열에 추가하기
			visited[i] = true;
			backtrack(curlen+1);		//순열의 현재길이를 하나 늘려 재귀
			visited[i] = false;	//재귀를 끝내고 다시 돌아왔으면 다른 분기 탐색을 위해 해당 글자의 visited를 false로 되돌리기
		}
	}

}