JArchive 프로그래밍 일기

줄 서는 방법 문제 링크 

리뷰 

줄 서는 k번째 방법을 출력해야한다. 

k는 n!이하의 숫자라고 하니깐 뭔가 규칙성이 있을 것 같았다. 

단순하게 next_permutation()으로 구현하니깐 정확성은 다 맞지만, 효율성에서 시간초과나서 틀렸다. 

n = 2 라면, 2가지 방법이 있다. 

[ 1, 2 ] 

[ 2, 1 ] 

n = 3개라면, 3! == 3 * 2 * 1 == 6가지 방법이 있다. 

[ 1 2 3] 

[ 1 3 2]

---------- 1번째, 2번째 방법은 앞자리가 1이다. 

[ 2 1 3]

[ 2 3 1]

--------- 3번째, 4번째 방법은 앞자리가 2다. 

[ 3 1 2]

[ 3 2 1]

--------  5번째, 6번째 방법은 앞자리가 3이다. 

일단 [ 1 2 3 ] 숫자가 들어있는 벡터 num_v를 만든다. 

k번째 방법을 (n-1)! 으로 나누면 idx번째 숫자가 들어갈 자리를 알아낼 수 있다. 

효율성에서 "시간 초과" 난 코드.

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

vector<int> solution(int n, long long k) {
  vector<int> answer;

  vector<int> permu_v;
  for(int i = 1; i <= n; i++) permu_v.push_back(i);

  do{
    k--;
    if(0 != k) continue;
    else{
      for(int i = 0; i < n; i++){
        answer.push_back(permu_v[i]);
      }
      break;
    }
  }while(next_permutation(permu_v.begin(), permu_v.end()));

  return answer;
}

"맞았습니다"코드

#include <vector>
#include <algorithm>
#define ll long long
using namespace std;

ll 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;

  long long idx, target_num;
  vector<int> num_v;
  for(int i = 1; i <= n; i++) num_v.push_back(i);

  while(0 < n){
    idx = factorial(n) / n;
    target_num = int((k-1) / idx); // answer에 넣을 숫자
    answer.push_back(num_v[target_num]);
    num_v.erase(num_v.begin() + target_num);
    n--;
    k %= idx;
    if(k == 0) k = idx;
  }

  return answer;
}