[프로그래머스] 줄 서는 방법 C++ 풀이 및 해설

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

프로그래머스

 

풀이 방법

• [1, 2, 3]
• [1, 3, 2]
• [2, 1, 3]
• [2, 3, 1]
• [3, 1, 2]
• [3, 2, 1]

첫번째 번호가 동일하게 반복되는 규칙이있다.

N이 주어졌을때 N-1만큼 첫번째 번호는 순서대로 동일한 값을 갖는다.

 

N-1이 주어졌을때 N-2만큼 첫번째 번호는 순서대로 동일한 값을 갖는다.

 

만약 N이 3일때 2만큼 첫번째 번호가 반복된다.

1, ...

1, ...

2, ...

2, ...

3, ...

3, ...

그리고 첫번째 번호를 제외시키고 다음 N-1인 2일때 (N-1)-1인 1만큼 동일한 값을 갖는다.

만약 첫번째 번호가 1이였었다면 남은 번호 2, 3이 1만큼 동일한 값을 갖는것이다.

 

아래의 참고 링크에서 설명이 잘 되어있으므로 참고하고. 부가적인 설명을 덧붙이겠다.

참고 : https://kangworld.tistory.com/258, https://ongveloper.tistory.com/133

sameArea?

sameArea는 동일한 첫번째 값이 반복되는 집합의 크기이다.

이 크기는 위에 설명했듯이 N일때 N-1만큼 반복된다.

 

index = k/sameArea?

k번째 결과를 구해야할때

sameArea만큼 첫번째 번호가 반복되므로

k/sameArea로 k의 위치에 따라 첫번째 번호가 무엇인지 구할 수 있다.

 

k%=sameArea?

k번째 결과의 첫번째 번호를 구했을때

다음 k번째 결과는 첫번째 번호의 앞선 번호들을 모두 제외한 번째 답을 구해야함으로

k를 sameArea로 나눈 나머지 번째 답을 구해야한다.

 

전체 코드

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

long long int 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;
    vector<int> number;
    
    // 1~n 번호 삽입
    for(int i=1; i<=n; i++) {
        number.push_back(i);
    }
    
    
    // 문제에서 주어진 k는 1~k번째 인덱스를 가지지만. 실제 number 배열은 0~k-1의 인덱스를 가짐
    // 그래서 k-1로 실제 배열과 인덱스를 맞춘다.
    k--;
    while(n>1) {
        // n이 1일때 factorial 계산이 안되므로 탈출
        // sameArea: 첫번째 번호가 동일한 집합의 크기
        long long int sameArea = factorial(n-1);
        
        // index: 첫번째 번호의 인덱스
        int index = k/sameArea;
        
        // k: 현재 찾아야할 k번째 방법
        k%=sameArea;
        n--;
        answer.push_back(number[index]);
        number.erase(number.begin()+index);
    }

    //n이 1일때 위의 while문에서 계산이 안되었으므로 남은 0번째 번호를 삽입
    answer.push_back(number[0]);
    
    
    return answer;
}