[java] 프로그래머스 - 줄 서는 방법

문제

프로그래머스-줄 서는 방법
n명이 사람이 일렬로 줄을 설 때 가능한 방법을 사전 순으로 나열했을 때 k번째 방법을 구하는 문제

• 제한 사항
  줄을 서는 사람의 수 n : n <= 20
  방법을 사전 순으로 나열했을 때 구할 순서 k : k <= n!

• 예시
  n = 3 일때 가능한 방법은 6가지다
  사전 순서대로 나열한다면

  1. [1, 2, 3]
  2. [1, 3, 2]
  3. [2, 1, 3]
  4. [2, 3, 1]
  5. [3, 1, 2]
  6. [3, 2, 1]
     k = 5일때 k번째 줄 서는 방법은 [3, 1, 2] 이다

풀이

ㅠㅠ 수학에 자신없는 나에겐 힘겨웠던 문제였다
n이 20이하이므로 전체 방법을 다 구하려면 시간이 터진다
가능한 방법은 n!이므로 아무리 k까지 연산을 돌린다고 해도 k가 n!이하이기 때문에 ❌❌

시행착오(효율성 시간초과)

처음 생각한 방법은 k를 이용해서 가장 앞의 원소를 구한다음, 그 이후부터 세어 나가는 방법이다
n = 3일 때 숫자 1이 제일 앞에 오는 경우의 수는 2번이다
n = 4일 때 숫자 1이 제일 앞에 오는 경우의 수는 6번이다
즉, n개의 원소를 나열하는 방법의 수 중에서 한 숫자가 가장 앞에 오는 경우의 수는 (n-1)!이다

이 (n-1)!와 k를 가지고 첫번째 원소와 그 원소 이후 몇번째를 구해야하는지 알 수 있다

  f = (n-1)!
  시작 원소 = k % f == 0? k / f : k / f + 1  
  이후 순서 = k % f == 0? f : k % f

• 예시

  n = 3, k = 5 // [3, 1, 2]
  f = (n-1)! = 2! = 2
  시작원소 = 5 % 2 == 0 ? 2 : 3
  이후 순서 = 5 % 2 == 0 ? 2 : 1

  • [3, _, _] 에서 남은 [1, 2]를 배치할때 사전 순 1번째 => [3, 1, 2]

하지만 이 방법도 n = 20이라면 남은 19자리를 배치해야해서 효율성에서 처참하게 시간이 터졌다

찐 풀이

위에서 했던 시행착오방법을 이용해서 남은 자리들도 같은 방식으로 맞춰나갔다
위의 시행착오는 첫번째 자리만 찾는 거였는데 이걸 다음자리에 적용하고 그 다음자리 .. 이런식으로 찾는다

	long last = k % fact == 0 ? fact : k % fact; // 이후(n-1)의 k
	long first = k % fact == 0 ? k / fact : k / fact + 1; // 시작원소
	int cnt = 0; // 몇번쨰인지를 세기 위함
	for (int i = 0; i < chk.length; i++) {
		if (!chk[i]) {
			cnt++;
			if (cnt == first) {
				answer[idx++] = i + 1; // 현재 자리에 들어올 값
				chk[i] = true;
				getNumber(n - 1, last, chk, fact / (n - 1));
			}
		}
	}

시행착오와 다른점은 first(시작원소)의 경우 숫자를 그자체가 아닌,
사용하지 않은 원소들 중 몇번째인지 라는 것이다

또한 (n-1)!를 계속 구하는 것이 아니라, 처음에 구한 값을 나눠가면서 적용한다
idx-1까지 왔다면 하나남은 원소를 마지막 인덱스에 넣어주고 종료한다

• 주의사항
  last(n-1에게 넘겨줄 k)는 long형의 k의 연산결과이므로 long을 해줘야한다

소스코드

import java.util.*;
class Solution {
	static long N;
	static int[] answer;
	static int idx;

	public int[] solution(int n, long k) {
		answer = new int[n];
		// factorial을 n으로 나눈 수, (n-1)! => 한 숫자가 가장앞에오는 경우의 수
		boolean[] chk = new boolean[n];
		N = n - 1;
		idx = 0;
		getNumber(n, k, chk, fac(n - 1));

		return answer;
	}

	private void getNumber(int n, long k, boolean[] chk, long fact) {
		if (idx == N) {
			for (int i = 0; i < chk.length; i++) {
				if (!chk[i]) {
					answer[idx] = i + 1;
					break;
				}

			}
			return;
		}
		long last = k % fact == 0 ? fact : k % fact;
		long first = k % fact == 0 ? k / fact : k / fact + 1;
		int cnt = 0;
		for (int i = 0; i < chk.length; i++) {
			if (!chk[i]) {
				cnt++;
				if (cnt == first) {
					answer[idx++] = i + 1;
					chk[i] = true;
					getNumber(n - 1, last, chk, fact / (n - 1));
				}
			}
		}
	}

	public long fac(int n) {
		long i = 1;
		for (int j = 2; j < n + 1; j++) {
			i *= j;
		}
		return i;
	}
}