[코딩테스트C++] 줄 서는 방법

오늘의 문제

https://programmers.co.kr/learn/courses/30/lessons/12936#

줄 서는 방법

나의 풀이

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

using namespace std;
long long Factorial(long long n){
    long long res =1;
    for(int i=1;i<=n;i++){
        res *= i; 
    }
    return res;
}
vector<int> solution(int n, long long k) {
    vector<int> answer;
    vector<long long > num;
    for(int i= 1;i<=n;i++){
        num.push_back(i);
    }
    int div = n-1;
    k--;
    while(div != 0){
        long long fdiv = Factorial(div);
        answer.push_back(num[k/fdiv]);
        num.erase(num.begin()+k/fdiv);
        k = k%fdiv;
        div--;
    }    
    answer.push_back(num[0]);
    return answer;
}

모범 답안

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

vector<int> setAlign(int n, long long cnt)
{
    vector<int> answer;
    for(int i=1;i<=n; i++) answer.push_back(i);

  long long i=1;
  do {
    if(cnt==i++) break;
  }while(next_permutation(answer.begin(),answer.end()));

    return answer;
}
int main()
{
    int testn = 3;
    long long testcnt = 5;
    vector<int> testAnswer = setAlign(testn,testcnt);
    // 아래는 테스트로 출력해 보기 위한 코드입니다.

    for(int i=0; i< testAnswer.size(); i++)
    {
        cout << testAnswer[i] << " ";
    }
}

배울 점

• 규칙성은 그려보면서 금방 찾을 수 있었다. 각 자리마다 올 수 있는 경우의 수를 나눠 자리수를 알아냈고 전체 벡터에서 쓴 숫자를 빼네어 다시 사용되지 못하게 했다. 남은것중 몇번째 숫자가 올지만 정해서 넣으면 된다.
• 규칙성은 나눈 몫, 나머지로 찾을 수 있었고 나눈 몫이 수 벡터의 인덱스가 될것이고, 나눈 나머지가 다음 나눌 숫자가 된다.
• 나눠지는 값은 팩토리얼로 구하면 된다. 코딩테스트 문제는 확률과 통계과목같다

• 뭐야 저런게 있냐 근데 저걸 돌리면 long long 범위의 커다란 loop를 돌아서 효율성이 만족되지 않는다. STL permutation 함수의 원리를 찾아봐야겠다.
• 최악 시간복잡도는 O(n)이다. 이코드에 사용되면 k * O(n) 이 되어 어마어마해진다