[알고리즘문제] 프로그래머스 -줄 서는 방법



n개의 숫자를 줄을 세울때(순열) k번째 수를 구하는 문제 입니다. 처음에 지원해주는 api로 먼저 한번 해봤는데 역시나 시간초과가 나왔습니다. 

 

먼저 문제에서 규칙을 한번 찾아봅시다. 3개의 숫자로 만들 수 있는 조합은 아래와 같습니다. 총 만들 수 있는 경우의 수는 6가지, 즉 n!으로 표현할 수 있습니다. 같은 예로 n개의 숫자인 경우 4! = 24개가 될 수 있습니다. 

 

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

예시에서 1이 제일 앞에 있는 경우, 2가 제일 앞에 있는 경우, 3이 제일 앞에 있는 경우는 각각 2개씩 존재합니다. 이 부분을 수학적으로 접근해보면 n! / n, (n-1)!로 표현할 수 있습니다. 

 

이를 생각해보면 총 경우의 수 / n개의 숫자, 즉 각각의 숫자는 몇개씩 줄을 세울 수 있냐, 몇개의 숫자를 표현할 수 있냐로 생각할 수 있습니다.

 

현재 n : 3, k : 5이기 때문에 n! / n을 하면 2가 나옵니다. 여기서 n! / 2를 slice로 표현하겠습니다. 다시한번 말하면 slice의 의미는 각 숫자가 맨 앞에 있는 경우의 수를 의미합니다(1은 [1,2,3], [1,3,2] / 2는 [2,1,3], [2,3,1]...)

 

문제로 돌아가서 k는  6가지 중에서 5번째 숫자를 구하라고 했고 slice는 2 입니다. 여기서 k / slice를 해보면 2가 나오는데, 여기서 2가 의미하는 앞자리가 [1,2]인 경우를 pass한다는 의미 입니다. 그렇다면 정확한 숫자를 구하진 않았지만 앞자리가 3은 구했네요.

 

이제 위와 똑같은 방법으로 다시 계산을 하면 됩니다. 단, 각각의 변수값, 범위가 조금 수정되는데 앞자리가 3이기 때문에 3인 경우는 다음과 같이 2가지의 경우가 나옵니다.

 

 

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

 

처음 n은 3이었는데, 3을 하나 구했기 때문에 2가지가 됩니다(1,2). 

 

그리고 k는 "몇번째"값을 구하는 것이였는데, 앞서 n이 3인 경우에는 5였지만 지금은 1이 됩니다. 이는 k % slice값인데, 이를 다시 생각해보면 k / slice은 몇개를 pass했느냐, 앞에서 k / slice = 2이기 때문에 [1,2]인 경우를 패스 하였고, k % slice = 1, 앞자리가 3인 경우에서 몇번째를 의미하느냐? 입니다. 이는 굉장히 중요한 부분입니다.

 

그렇기 때문에 위의 예시에서 1번째 값인 1이 구해집니다. 문제를 구하는 방법은 위와 같은 로직으로 돌아가고, 이제 코드로 어떻게 구현하였는지 한번 보겠습니다.

#include <string>
#include <vector>
#include <iostream>

using namespace std;


long long factorial(int n){
    long long result = 1;
    for(int i=1;i<=n;i++){
        result*=i;
    }
    return result;
}

vector<int> solution(int n, long long k) {
    
    vector<int> answer,nums;
    
    k--;
    for(int i=1;i<=n;i++){
        nums.push_back(i);
    }

    while(n > 0){
        long long slice = factorial(n-1);
        int index = k / slice;
        answer.push_back(nums[index]);
        nums.erase(nums.begin() + index);
        k %= slice;
        n--;
    }
    return answer;
}

 

1. 먼저 factorial()함수는 입력받은 n정수의 팩토리얼 값을 반환해 줍니다.

2. nums는 1~n까지의 값을 저장하는 벡터로, 맨 앞자리 값을 구하는데 사용합니다.

3. 처음 k--해준 이유는, n번째는 실제로 벡터의 n-1인덱스에 그 값이 존재하기 때문이빈다.

 

전체 코드는 while문에서 끝나며 남은 숫자가 0보다 클때까지 반복합니다.

slice값은 각각의 숫자[1,2,3]이 몇개를 표현할 수 있는지를 의미합니다.1인 경우는 [1,2,3], [1,3,2], 2인 경우는 .....

그리고 index는 k번째를 slice로 나눈 몫을 의미하며 이는 맨 앞에있는 값을 의미합니다(실제로는 nums[index]값을 의미합니다.)

그리고 nums[index]값을 사용 했으니 해당 위치의 값을 지워줍니다. 

 

다시 k %= slice을 해주는데, 이는 

 

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

에서 다시 k번째 값을 찾기 위함입니다. 물론 3을 찾았기 때문에 n--을 해줍니다.