프로그래머스 - 줄 서는 방법(Level 3)/Wanna Be 컴잘알

문제 출처- https://programmers.co.kr/learn/courses/30/lessons/12936

코딩테스트 연습 - 줄 서는 방법 | 프로그래머스

 

-문제-

 

n명의 사람이 일렬로 줄을 서고 있습니다. n명의 사람들에게는 각각 1번부터 n번까지 번호가 매겨져 있습니다. n명이 사람을 줄을 서는 방법은 여러가지 방법이 있습니다. 예를 들어서 3명의 사람이 있다면 다음과 같이 6개의 방법이 있습니다.

• [1, 2, 3]
• [1, 3, 2]
• [2, 1, 3]
• [2, 3, 1]
• [3, 1, 2]
• [3, 2, 1]

사람의 수 n과, 자연수 k가 주어질 때, 사람을 나열 하는 방법을 사전 순으로 나열 했을 때, k번째 방법을 return하는 solution 함수를 완성해주세요.

제한사항

• n은 20이하의 자연수 입니다.
• k는 n! 이하의 자연수 입니다.

---

입출력 예

n	k	result
3	5	[3,1,2]

 

 

 

-접근-

1. dfs로 모든 경우의 수를 구하여 찾는 경우에는 정확도 검사는 통과하지만 효율성 검사에서 실패가 뜨게되기 때문에 특정 번째수를 바로 찾을 수 있는 방법을 사용해야합니다.

2. 예제를 기준으로 설명을 하자면 n=3일때 모든 경우의 수는 factorial(n)입니다.

3*2*1 = 6 인데,

[1,2,3]의 순열을 나열시켜보면

 

1,2,3

1,3,2

2,1,3

2,3,1

3,1,2

3,2,1

이다.

 

여기서 앞자리 기준으로 나눠보면

1,2,3

1,3,2

---------

2,1,3

2,3,1

---------

3,1,2

3,2,1

 

도막수 =n이고 1도막에 factorial(n)/n개씩 나오게된다.

위의 예에선 도막수는 3도막, 1도막에 factorial(3)/3 = 2개이다.

 

1,2번째는 맨 앞이 1  -> index로 따지면0 

3,4번째는 맨 앞이 2  -> index로 따지면1

5,6번째는 맨 앞이 3  -> index로 따지면2

 

k-1 / 1도막의 개수 -> if(k==5)이면 5/2 =  2가 나온다. (index로 바로 매칭시키면된다.)

 

(k로 안하고 k-1로 하는 이유는 k가 6인경우에  k/2 는 3이나오는데 빼줘야하기 때문이다. k-1로 하면 index와 바로바로 매칭이 가능하다.)

 

인덱스를 찾으면 해당 인덱스를 answer 벡터에 삽입하고 기존의 인덱스에서 넣은 값은 erase해준다.

 

k=5였으므로 다음으로 봐야할 부분은 해당 도막을 보면된다.

 

 

---------

3,1,2

3,2,1

---------

여기서 3,1,2를 찾아야하므로 k=1이다. 

이걸 식으로 도출해내려고 하면 k= k%1도막의 개수(2)이다. 따라서 1번째를 찾는거고

 

여기서 도막의 개수는

첫번째 인덱스가 정해졌으니 n-1이 되고 

도막당 개수는 factorial(n-1)/n-1 = 1이 된다.

 

이것을 계속 반복하게되면 답을 구할 수 있었다.

 

-코드-

#include <string>
#include <vector>
#include <iostream>
#include <math.h>
using namespace std;

long long factorial(int n) {
	if (n == 1)
		return 1;
	else
		return n * factorial(n - 1);
}

vector<int> solution(int n, long long k) {
	vector<int> answer;
	vector <int> v;
	long long slice, now;
	
	for (int i = 1; i <= n; i++)
		v.push_back(i);

	while (1) {
		if (n == 0) {
			break;
		}

		slice = factorial(n) / n;
		now = int((k - 1) / slice);
		answer.push_back(v[now]);
		v.erase(v.begin()+now);
		n--;
		k %= slice;
		if (k == 0)
			k = slice;
	}
	
	return answer;
}