#############
문제
#############
a,b,c,d,e,f,g,h의 8개 영문자로 만들 수 있는 순열수는 8! = 40,320이다.
이 순열들을 사전 순서로 배열하고 이들의 순서를 적어보면 아래와 같다.
|
문자열 |
순서 |
|
abcdefgh |
1 |
|
abcdefhg |
2 |
|
abcdegfh |
3 |
|
... |
... |
|
fbhacdeg |
26521 |
|
... |
... |
|
hgfedcba |
40320 |
이렇게 8개의 영문자로 만들어진 순열이 주어질 때, 이 순열이 몇 번째에 나오는지를 출력하는 프로그램을 작성하라.
입력: 8개의 영문자열 ex)fbhacdeg
출력: 입력된 영문자열의 순열 번호 ex)26521
###############
풀이
###############
이 문제는 n개의 문자에 대해서 순서를 바꿔서 표현할 수 있는 방법을 묻는 '문자열에 대한 순열조합(Permutation)'문제를 응용한 것이라 볼 수있다. 해서, 문자열에 대한 Permutation을 푸는 방법인 재귀호출을 써서 각 문자열조합 케이스를 만들어 내고, 문제에서 주어진 해당 문자열이 나올 때 멈춰서 이 때의 카운트를 출력하게 할 수 도 있다.
그러나 여기서는 이렇게 해당 문자열을 만들어 나가면서 비교하는 방식이 아닌, 순열의 가지는 특성을 이용해서 수치적으로 순서를 알아내고자 한다. 이렇게 하면, 각 문자열을 n! 시간만큼 만들어나가지 않아도 되므로, 쉽게 해당문자열의 번호를 알아낼 수 있다.
8개의 문자열 중에서, 첫번째 문자 위치에 'a'가 들어간 문자열의 순서번호는 1에서 7! 까지가 될것이다. (왜냐면 첫번째를 a로 고정하고, 나머지 7개의 문자로 만들 수 있는 경우의 수는 7! 이므로)
만약에 첫번째 문자가 'b'라면 (7! + 1) 에서 (7! + 7!)까지, 'c'라면 (7! + 7! + 1) ~ (7! + 7! + 7!), 'd'라면 ((7! + 7! + 7!) ~ (7! + 7! + 7! + 1) ...
a: 1 ~ 7!
b: 1 + 7! ~ 2 x 7!
c: 1 + 2 x 7! ~ 3 x 7!
d: 1 + 3 x 7! ~ 4 x 7!
..
h: 1 + 7 x 7! ~ 8 x 7! --> 8 x 7! = 8!
이렇게 보면, 첫번째 문자가 무엇이냐에 따라서는 규칙성을 발견할 수 있겠다. 이제 두번째 문자에 따른 규칙성을 찾아보자.
첫번째 문자가 'a' 였을 때 두번 째 문자에 따른 순서번호를 생각해보자.
만약 두번 째 문자가 'b'라면(a가 첫번째 문자로 이미 사용되었으므로, bcdefgh 중 가장 순서가 빠른 문자는 b), 순서는 1 ~ 6! 이다.
왜냐면 두 개의 문자를 고정했기에 남은 문자 6개로 만들 수 있는 경우의 수는 6! 이므로.
두번째 문자가 'c'의 경우는 (6! + 1) ~(6! + 6!) = ((6! + 1) ~(2 x 6!)
'd'의 경우는 (2 x 6! + 1) ~(3 x 6!)
'e'의 경우는 (3 x 6! + 1) ~(4 x 6!)
...
첫번째 문자가 'b'였을 때 두번 째 문자에 따른 순서를 생각해 보자.
'b'로 시작하는 경우는, 첫번째 문자가 'a'인 경우수 7! 다음이기에, 시작은 7! + 1
'a'의 경우는 (남아있는 a c d e f g h 중 가장 첫번째 문자), (7! + 1) ~ (7! + 6!)
'c'의 경우는, (7! + 6! + 1) ~ (7! + 2 x 6!)
'd'의 경우는 (7! + 2 x 6! + 1) ~ (7! + 3 x 6!)
...
이제 전체에 대한 규칙성을 생각해보면, 다음과 같은 공식을 생각할 수 있겠다.
orderNum = 1+ rank(arr[0] in arr[0..7]) * 7! + rank(arr[1] in arr[1..7]) * 6!) + ... + rank(arr[6] in arr[6..7]
만약 'abcdefgh'의 경우라면,
arr[] = {a,b,c,d,e,f,g,h}가 되고, rank(arr[0] in arr[0..7]) = 0 이다. 왜냐면 arr[0] = 'a'이고, 이는 a~h중에서 가장 처음에 있는 문자.
마찬가지로 rank(arr[1] in arr[1..7]) = rank('b' in {b~h}) = 0
이렇게 계산하면, orderNum=1이 된다.
만약 'bcadefgh'의 경우라면,
rank(arr[0] in arr[0..7]) = 1
rank(arr[1] in arr[1..7]) = rank('c' in {c,a,d,e,f,g,h}) = 1
rank(arr[2] in arr[2..7]) = rank('a' in {a,d,e,f,g,h}) = 0
rank(arr[3] ...) =0
따라서, orderNum = 1 + 1 x 7! + 2 x 6! = 1 + 5040 + 720 = 5761
여기서, rank는 어떻게 구할까?
일반적인 방법은, 문자들을 소팅하고, 주어진 문자가 어느 위치에 있는지를 찾는 것이다.
이렇게 해도 되겠지만, 여기서는 좀 더 탐색시간이 짧은 방법으로 해봤다.
abcdefgh 중에서, 한 개 문자에 대한 순서를 찾는 것은, 그 해당 문자가 'abcdefgh'의 어느 위치에 있는지를 찾으면 된다.
만약 'c'를 찾는 것이면 rank({a,b,c,d,e,f,g,h},'c')는 2가 리턴되고, {a,b,c,d,e,f,g,h}는 {a,b,0,d,e,f,g,h}가 된다.
다시 'e'를 찾게되면 rank({a,b,0,d,e,f,g,h},'e')가 되어 3이 리턴되고, 남아있는 배열은 {a,b,0,d,0,f,g,h}이 된다.
이렇게 하면, 한 번 찾은 문자는 0으로 바뀌고, 이를 카운트하지 않으면, 남아있는 문자들 중에서의 순서를 찾을 수 있을 것이다.
###############
소스
###############
package p1;
import java.util.Scanner;
public class CharacterSequence {
public CharacterSequence(){
test();
}
private void test(){
String str = "hgfedcba";
/**
Scanner scanner = new Scanner(System.in);
System.out.println("Enter character set to know the sequence order num(ex. fbhacdeg)");
str = scanner.next();
*/
long order = calculateOrderNum(str);
System.out.println("Order is "+ order);
}
private long calculateOrderNum(String str){
byte[] tgtArr = str.getBytes();
byte[] orderedArr = "abcdefgh".getBytes();
long orderNum = cal(orderedArr,tgtArr);
return orderNum;
}
/**
* arr[0..7]
* orderNum = 1+ rank(arr[0] in arr[0..7]) * 7! + rank(arr[1] in arr[1..7]) * 6!) + ... + rank(arr[6] in arr[6..7]
* @param orderedArr
* @param tgtArr
* @return
*/
private long cal(byte[] orderedArr, byte[] tgtArr){
byte[] arr = new byte[orderedArr.length];
System.arraycopy(orderedArr, 0, arr, 0, arr.length);
int i=0;
long orderNum=1;
do{
orderNum += (rank(arr,tgtArr[i]) * factorial(7-i));
}while(i++ < 6);
return orderNum;
}
private int rank(byte[] arr, byte c){
int i=0;
int rank=0;
do{
if(arr[i] == 0){
continue;
}else if(c == arr[i]){
arr[i] = 0;
break;
}else{
rank++;
}
}while(i++ < arr.length);
return rank;
}
private long factorial(long n){
if(n<=0) return 0;
if (n==1) return 1;
return (n*factorial(n-1));
}
public static void main(String[] args) {
new CharacterSequence();
}
}
-끝-
'알고리즘 > 알고리즘(Java)' 카테고리의 다른 글
| 05. 거스름돈 계산 문제 (0) | 2015.03.30 |
|---|---|
| 04. 타일 채우기 가능여부 판단 알고리즘 (0) | 2015.03.30 |
| 03. 게시판 포스트 중첩부분 면적 구하기 (0) | 2015.03.27 |
| 01. Factorial, Permutation, Combination (0) | 2015.03.18 |
| 00. 시작하기, 준비하기 (0) | 2015.03.13 |