Level3 - 줄서는 방법

연구하는개발자 2021. 2. 26. 23:57

728x90

programmers.co.kr/learn/courses/30/lessons/12936

코딩테스트 연습 - 줄 서는 방법

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

programmers.co.kr

#include <string>
#include <vector>
#include <cstring>
using namespace std;

long long fac[21];
bool check[21];
void fact(){
    
   fac[0] = 1;
    for (int i = 1; i <= 20; i++) 
        fac[i] = fac[i - 1] * i;

}


vector<int> solution(int n, long long k) {
    vector<int> answer;
    vector<bool> check(n, false);
    fact();
    int s = 0;
    
    while(answer.size()!=n){
        for(int i=0; i<n; i++){
            if(check[i]==false){
                long long num = fac[n-1-s];
                if(k>num){
                    k-=num;
                    continue;
                }
                s++;
                answer.push_back(i+1);
                check[i]=true;
                break;
            }
        }
    }
    
    
    return answer;
}

예> n=4 일때, k = 10일때

while문 첫번째

4!/4 = 3! = fac[3] = 6 = num 이다.

i=0 일 때 k>num , k=10-6=4

i=1 일 때 k<num -> 2 selected

while문 두번째

3!/3 = 2! = fac[2] =2 =num

i=0 일 때 k(=4) > num(=2), k=4-2=2

i=1 check[i] = true

i=2 일 때 k(=2)==num(=2) -> 3 selected

네 번째까지 반복하면 {2,3,4,1} 이나온다.