[백준온라인] 9742번 순열

문제 : https://www.acmicpc.net/problem/9742

9742번: 순열

문제 요약 : 회사원의 출퇴근 기록을 입력받아 남아있는 사람 출력

입력	출력
1 ≤ 문자(길이) ≤ 10 1 ≤ 순열위치 ≤ 3628800	주어진 문자열의 주어진 순열 위치에 해당하는 문자 출력

 

JAVA

소스코드 : https://github.com/cbkpar/BOJ/blob/main/boj_9742.java

채점 번호	아이디	문제 번호	결과	메모리	시간	언어	코드 길이
30636038	cbkpar	9742	맞았습니다!!	16060KB	160ms	Java 11	1016B

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

public class Main {
	
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		String str,ch;
		int sz,l,i;
		int[] len = {1,1,2,6,24,120,720,5040,40320,362880,3628880};
		while((str=br.readLine())!=null) {
			StringTokenizer st = new StringTokenizer(str);
			ch = st.nextToken();
			sz = ch.length();
			l = Integer.parseInt(st.nextToken());
			sb.append(ch+" "+l+" = ");
			if(l>len[sz]) {
				sb.append("No permutation\n");
				continue;
			}
	        ArrayList<Character> q = new ArrayList<Character>();
	        for(i=0;i<sz;i++) q.add(ch.charAt(i));
	        l--;
	        for(i=sz-1;i>=0;) {
	        	sb.append(q.remove(l/len[i]));
	        	l %= len[i--];
	        }
	        sb.append("\n");
		}
		System.out.println(sb);
	}
}

주어진 문자열을 한 글자 씩 ArrayList에 넣어준다.

 

주어진 순열 순서가 주어진 문자열로 만들 수 있는 최대 순열 개수보다 클 경우

No permutation이라는 문자를 출력하고 넘어간다.

 

주어진 순열 순서가 주어진 문자열로 만들 수 있는 최대 순열 개수보다 작을 경우

순열의 순서를 0번째부터 계산하기 위해 입력된 순서에서 1을 빼준 후 다음과 같이 계산한다.

(ArrayList의 크기-1) 의 팩토리얼 값만큼 주어진 순서를 나눠준다.

해당하는 값에 대한 ArrayList값을 출력 후 제거한다.

ArrayList의 크기가 0이 될 때까지 반복한 후 모든 문자열을 사용 후 종료.

 

*) while((str=br.readLine)==null)

위 코드를 사용하면 개수가 정해지지 않은 입력 케이스를 모두 받아들일 수 있다.

 

예제 ) 

tuvwxyz 4000