c++ 프로그래머스_"줄 서는 방법"

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

프로그래머스

 

순열을 구하는 건데

기존에 구하는 방식으로 구하면

엄청 오래 걸려서 시간 초과 걸릴 거 같았다.

​

그래서

배열을 점점 줄여나가면서 원소를 교체해주는 방식으로 했다.

​

문제의 예는

1 2 3

3자리다

그럼

​

문제예시처럼

1 2 3

1 3 2

...

3 1 2

3 2 1

나온다.

​

맨 앞의 숫자가 변하는 단위는 2이다

즉 (n-1)! 이다.

​

(ex n = 4 이면

1 2 3 4

12 4 3

...

1 4 2 3

1 4 3 2

* 여기까지 6개 즉 , (n-1)! = (4-1)! = 6

2 1 3 4

...

​

그래서 나누는 단위를 구하고

몫을 보고 어디에 속하는지 ,

몇번째 인덱스를 보고 swap을 하는지.

그리고 n (사이즈) 도 줄여주면서 배열의 크기를 점점 작게 만들어

top - down 방식으로 진행했다.

​

( 1234 를 구하고 k 가 더 남았으면

234 에서 구하고 또

34 에서 구하는 방식 )

​

그리고 k%per == 0 일 때가 마지막이다.

그때는 swap할 거는 하고

내림차순! 으로 정렬해줘야된다.

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

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

    for (int i = 0; i < n; i++) {
        answer[i] = i + 1;
    }
    long long per = 1;
    int index = 0; 
// 배열의 크기가 하나씩 줄어드니 그에 맞게 맨 앞, 교체해야 할 인덱스 증가해주어야 됨
    
    while (n>0) {
        per = 1; // 단위
        for (int i = n - 1; i > 0; i--) {
            per *= i;
        }

        if (k % per == 0) {
            int now = k / per + index - 1;
            swap(answer[index], answer[now]);
            index++;
            sort(answer.begin() + index, answer.end(),greater<>());
            break;
        }
        else {

            int now = k / per + index;
            swap(answer[index], answer[now]);
            index++;

            sort(answer.begin() + index, answer.end());
            k = k % per;
           
            n--;
        }
    }

    return answer;
}