[프로그래머스 C++] 줄 서는 방법

 

[프로그래머스 C++] 줄 서는 방법

 

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

프로그래머스

---

 

해결방안

 

순열 Permutation, 조합 Combination

---

 

 

처음 시도한 코드 - 테스트 케이스 모두 통과. 효율성 테스트 시간 초과

 

#include <string>
#include <vector>
using namespace std;
 
vector<int> answer, temp;
int ch[21];
int cnt;
 
void Combination(int idx, const int& n, const long long& k)
{
    if(idx == n+1){
        cnt++;
 
        if (cnt == k){
            for (int i = 1; i <= n; i++)
                answer.push_back(temp[i]);
        }
 
        return;
    }
 
    for(int i = 1; i <= n; i++)
    {
	    if(ch[i] == 0)
        {
            ch[i] = 1;
            temp[idx] = i;
            Combination(idx+1, n, k);
            ch[i] = 0;
	    }
    }
}
 
vector<int> solution(int n, long long k) {
    
    temp.resize(n+1);
 
    Combination(1, n, k);
 
    return answer;
}

 

모든 조합을 다 검사하는 방법. 

시간초과.

 

 

 

 

 

 

#include <vector>
#include <algorithm>
using namespace std;
 
vector<int> solution(int n, long long k)
{
    vector<int> answer;
    for(int i = 1; i <= n; i++) 
        answer.push_back(i);
 
    long long i = 1;
    do {
        if(k == i++) break;
    }while(next_permutation(answer.begin(),answer.end()));
 
    return answer;
}

 

모든 조합을 다 검사하는 방법. 

시간초과.

 

 

 

 

 

 

---

 

 

정답코드

 

#include <vector>
#include <algorithm>
using namespace std;
 
vector<int> solution(int n, long long k) {
 
    vector<int> answer; // 결과를 저장할 벡터 초기화
    vector<int> temp(n);
    vector<long long> fact(n, 1); // 팩토리얼을 저장할 벡터 초기화, 첫 번째 요소는 1로 설정
 
    for (int i = 1; i < n; i++) // 팩토리얼 계산 (1부터 (n-1)까지)
        fact[i] = fact[i - 1] * i;
 
    for (int i = 0; i < n; i++) // 순열을 위한 벡터 초기화 (1부터 n까지)
        temp[i] = i + 1;
 
    k--; // k를 0-based 인덱스로 조정
 
 
    for (int i = 0; i < n; i++) // 각 위치에 대해
    {
        int idx = k / fact[n - i - 1]; // k를 현재 위치의 팩토리얼로 나눈 몫을 이용해 해당 위치에 올 숫자를 순열에서 찾음
        
        answer.push_back(temp[idx]);
        temp.erase(temp.begin() + idx); // 찾은 숫자를 순열에서 제거
 
        k %= fact[n - i - 1]; // k를 현재 위치의 팩토리얼로 나눈 나머지로 업데이트
    }
 
    return answer;
}

 

이 문제는 입력으로 주어진 n개의 숫자에 대해 k번째 순열을 찾는 것이 목표다.

 

이를 위해 팩토리얼을 이용하여 각 위치에 올 숫자를 직접 계산한다. 이렇게 하면 모든 순열을 생성하지 않고도 k번째 순열을 구할 수 있다.

 

핵심은 k를 현재 위치의 팩토리얼로 나눈 몫과 나머지를 이용하는 것이다. 몫은 현재 위치에 올 숫자의 인덱스를 결정하고, 나머지는 다음 위치에 올 숫자를 결정하기 위한 새로운 k를 제공한다.

---