9742. 순열 [BAEKJOON / JAVA]
문제
https://www.acmicpc.net/problem/9742
9742번: 순열
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 문자열은 서로 다른 숫자와 알파벳으로 이루어져 있으며, 길이는 최대 10이다. 또한, 사전
www.acmicpc.net
집합의 순열이란 집합의 서로 다른 원소를 모두 사용해 만들 수 있는 순서이다. 예를 들어, {2,3,5}의 순열은 다음과 같다.
- 2 3 5
- 2 5 3
- 3 2 5
- 3 5 2
- 5 2 3
- 5 3 2
각각의 순열은 숫자로 나타낼 수 있다. 위의 순열은 사전순으로 쓰여져 있으며, 등장하는 순서를 이용해 나타낸다. 즉, 3 5 2는 위치 4에 있고, 5 3 2는 마지막 위치인 6에 있다.
첫 번째 문자열은 서로 다른 숫자와 알파벳으로 이루어져 있으며, 길이는 최대 10이다. 또한, 사전순 순서대로 주어진다. 문자열 다음에는 찾아야 하는 위치가 주어지며, 이 값은 3,628,800보다 작거나 같은 자연수이다.
input =
235 4
bein 20
123456 700
mnpqr 130
tuvwxyz 4000
output =
235 4 = 352
bein 20 = nbie
123456 700 = 651342
mnpqr 130 = No permutation
tuvwxyz 4000 = ywuxvzt
전체코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static boolean [] isSelected;
static int [] selection;
static String word = "";
static char[] arr;
static int N, R, cnt; // 입력값 정수, 입력값 문자열 길이,
static void permutation(String word, int r){
if (r == R){
cnt++;
if (cnt == N){
System.out.print(word + " " + N + " = ");
for (int i=0; i<R; i++){
System.out.print(word.charAt(selection[i]));
}
System.out.println();
}
return;
}
for (int i=0; i < R; i++){
if (isSelected[i]) continue;
isSelected[i] = true;
selection[r] = i;
permutation(word, r+1);
isSelected[i] = false;
}
}
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
while ((word = bf.readLine()) != null && !word.isEmpty()){
st = new StringTokenizer(word, " ");
word = st.nextToken().toString();
N = Integer.parseInt(st.nextToken());
cnt = 0;
R = word.length();
isSelected = new boolean[R];
selection = new int [R];
int fac=1;
for (int i=1; i<=R;i++){
fac = i*fac;
}
if (fac < N){
System.out.println(word + " " + N + " = " + "No permutation");
}
else {
permutation(word, 0);
}
}
}
}
로직
- 입력값을 받을 때 입력값을 받는 횟수 및 조건이 없기 때문에 EOF 처리를 해준다.
- 선택여부를 표시하는 boolean타입의 isSelected를 생성한다.
- selection 변수를 만들어줄 단어 길이만큼 배열을 생성한 뒤 순열할 인덱스 값을 할당한다.
- 순열을 조합할 길이가 되었을 경우 selection을 통해 순열을 출력한다.
코드 디테일
입력값 받기 및 EOF 처리
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
while ((word = bf.readLine()) != null && !word.isEmpty()){
st = new StringTokenizer(word, " ");
word = st.nextToken().toString();
N = Integer.parseInt(st.nextToken());
cnt = 0;
R = word.length();
isSelected = new boolean[R];
selection = new int [R];
입력값을 받을 횟수는 알지 못하기 때문에 while문을 통해 입력값을 받는다.
이때 입력값이 끝나는 특정 조건 입력값이 없기 때문에 EOF 처리를 해주어야 한다.
word는 순열할 입력값을 받는다.
while ((word = bf.readLine()) != null && !word.isEmpty()){
만약 word에 아무런 입력값이 들어오지 않을 시 입력받는 것을 멈춘다.
st = new StringTokenizer(word, " ");
word = st.nextToken().toString();
N = Integer.parseInt(st.nextToken());
StringTokenizer를 통해 공백이 존재하는 입력값을 구분할 수 있도록 한다.
순열을 진행할 word를 받고, 순열 후 N번째의 값을 출력하기 위해 정수 N의 입력값을 받는다.
cnt = 0;
R = word.length();
isSelected = new boolean[R];
selection = new int [R];
N번째의 순열을 출력하기 위해 cnt를 생성하고,
조합 및 출력할 길이 R을 설정한다.
순열을 위한 조합이 중복되지 않도록 boolean타입의 isSelected를 생성한다.
마지막으로 순열하기 위한 word의 인덱스를 저장 및 출력할 배열 selection을 R 길이만큼 생성한다.
순열 실행
for (int i=0; i < R; i++){
if (isSelected[i]) continue;
isSelected[i] = true;
selection[r] = i;
permutation(word, r+1);
isSelected[i] = false;
}
R길이만큼 순열조합을 위해 for문 실행 범위를 R만큼 설정한다.
if (isSelected[i]) continue;
만약 해당 순서의 문자가 선택했던 문자라면 (true라면) 넘어가준다.
선택했던 문자가 아니라면 아래 구문을 실행하도록 한다.
isSelected[i] = true;
selection[r] = i;
permutation(word, r+1);
해당 문자를 선택하였으므로 true처리를 해준다.
selection 배열의 r 인덱스에 i값을 할당해준다.
그리고 자기자신(permutation) 메소드를 불러준 뒤
if (r == R){
cnt++;
if (cnt == N){
System.out.print(word + " " + N + " = ");
for (int i=0; i<R; i++){
System.out.print(word.charAt(selection[i]));
}
System.out.println();
}
return;
}
이 구문을 실행시키도록 한다.
자기 자신을 호출하는 재귀를 표현하면 이러하다.
코드로 볼 때는 똑같은 for문이지만 사실 각기 다른 for문이다.
현재 우리가 순열조합할 단어의 길이가 3이므로 하나의 for문을 3번 반복한다.
처음 반복문을 실행했을 경우 모든 문자를 선택하였기 때문에 isSelected의 값은 모두 true이다.
selection의 작동원리를 보자면 재귀 실행 시 실행값 r에 1씩 더해주며 word 순열조합을 실행한다.
이때 모든 조합의 중복이 없어야 하므로 isSelected의 true값을 조건문으로 걸어놓는 것이다.
permutation(word, r+1);
isSelected[i] = false;
하나의 순열조합을 마친 뒤 (재귀 실행 후) 방금 조합하였던 문자를 false로 바꿔주어 다시 문자를 조합할 수 있도록 한다.
재귀 실행을 마치고 선택여부를 다시 false로 바꿔줄 때
우리가 눈으로 보이는 for문의 i값은 2가 아닌 1이 된다.
앞서 말했듯이 같은 for문을 실행시키는 것 같지만 각기 다른 for문을 실행하고 있기 때문이다.
for문을 실행하고 실행값 r을 1씩 더해주며 재귀를 실행하면 위 그림과 같이 isSelected와 selection의 값이 다르게 변해있다.
위 그림으로 다시 순열을 조합한다면
이러한 형식으로 새로운 순열을 생성한 것이다.
재귀 종료 조건 및 출력 조건 실행
if (r == R){
cnt++;
if (cnt == N){
System.out.print(word + " " + N + " = ");
for (int i=0; i<R; i++){
System.out.print(word.charAt(selection[i]));
}
System.out.println();
}
return;
}
실행값 r이 R과 같다는 뜻은 조합할 문자의 개수로 설정해둔 3과 for문(재귀)를 통해 조합한 (selection) 문자열 길이와 같을 때를 말하는 것이다.
이 구문으로 순열 조합 시 길이가 3만큼 실행하고 재귀를 종료시킬 수 있다.
cnt를 이용하여 순열조합 순서 중 원하는 순서를 출력할 수 있도록 카운트한다.
for (int i=0; i<R; i++){
System.out.print(word.charAt(selection[i]));
}입력값으로 받은 N(순서)가 현재 진행 중인 순서(cnt)일 때 해당 순열을 하나씩 출력하게 된다.
예외처리
int fac=1;
for (int i=1; i<=R;i++){
fac = i*fac;
}
if (fac < N){
System.out.println(word + " " + N + " = " + "No permutation");
}
else {
permutation(word, 0);
}
모든 순열 조합의 수는 팩토리얼이다.
모든 경우의 수를 for문을 통해 계산하고,
입력값으로 받은 순서 N이 모든 경우의 수보다 많을 경우, 즉 순서의 순열조합이 존재하지 않을 경우 "No permutation"을 출력할 수 있도록 fac < N 조건문을 실행하도록 한다.