[C++로 풀이] 줄 서는 방법 (경우의 수 O(n!) 피하기)⭐⭐⭐

📌 줄 서는 방법

난이도 ⭐⭐⭐

🚀 문제

🚀 내 풀이

✈ 1 차 풀이 ❌ (+시간초과⏰)

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> solution(int n, long long k) {
    vector<int> answer(n);
    
    vector<string> q(n);
    for(int i = 0; i < n; ++i)
        q[i] = to_string(i + 1);
    
    long long count = 1;
    do{
        if (count++ == k)
            break;
    }while(next_permutation(q.begin(), q.end()));
    
    for(int i = 0; i < n; i++)
        answer[i] = stoi(q[i]);
    
    return answer;
}

단순하게 모든 순열을 다 구하되 k번째의 순열에서 멈추는 식으로 코드를 짰었다. 사전 순서 크기를 기준으로 다음 순열이 결정될 수 있도록 string 벡터의 순열을 구했었다.

역시 이렇게 단순하게 풀릴 문제였으면 레벨 3 문제가 아니였겠즤..?ㅠ ㅠ

이렇게 모든 순열을 구해나가는 경우엔 O(n!) 시간 복잡도에 도달하게 된다. 그러니 다른 방법을 찾아야 한다.

굳이 처음부터 순열을 1번째부터 k번째까지 구하지 않아도, k번째의 순열의 위치가 어디일지 알아낼 수가 있다.

✈ 2 차 풀이 ⭕

💡 k번째 순열이 어떤 모습인지 순회하지 않고 바로 알아내는 방법

n = 4, k = 16 을 예로 들어 보자. 즉 [1, 2, 3, 4]로 이루어지는 순열의 16번째 순열이 어떤 모습인지 규칙을 찾아내보자.

• [1, 2, 3, 4] 즉 n = 4의 순열은 총 4! = 24가지가 나올 수 있다. 4! 는 4 * 3! 와도 같다.
  • [1,2,3,4] 순열 순서의 규칙 (총 4 * 3! = 24개) 📢 [1,2,3,4] 순열 내에서 16 번째 찾기
    • 3! = 6 개 👉 1 로 시작하는 [2, 3, 4] 순열 👉 1 ~ 6(=1x3!) 번째
    • 3! = 6 개 👉 2 로 시작하는 [1, 3, 4] 순열 👉 7 ~ 12(=2x3!) 번째
    • 3! = 6 개 👉 3 로 시작하는 [1, 2, 4] 순열 👉 13 ~ 18(=3x3!) 번째
    • 3! = 6 개 👉 4 로 시작하는 [1, 2, 3] 순열 👉 19 ~ 24(=4x3!=4!) 번째
  • 16번째 순열은 2 x 3! < 16 <= 3 x 3! 을 만족하기 때문에 3 으로 시작하는 [1, 2, 4] 순열 에 위치할 것이라는 것을 알 수 있다!!
    • ✔ “16번째 순열의 첫 번째”는 무조건 3이 된다는 것을 확인할 수 있다. 16번째가 3으로 시작하는 순열인 13번째~18번째에 속하기 때문이다. 이제 [3] 은 확정됐으니 남은 [1,2,4] 순열 내에서 16 - 12 = 4 번째에 해당하는 순열을 찾으면 된다.
      • [1,2,4] 순열 순서의 규칙 (총 3 * 2! = 6개) 📢 [1,2,4] 순열 내에서 4 번째 찾기
        • 2! = 2개 👉 1 로 시작하는 [2, 4] 순열 👉 1 ~ 2(=1x2!) 번째
        • 2! = 2개 👉 2 로 시작하는 [1, 4] 순열 👉 3 ~ 4(=2x2!) 번째
        • 2! = 2개 👉 4 로 시작하는 [1, 2] 순열 👉 5 ~ 6(=3x2!) 번째
      • 4번째 순열은 1 x 2! < 4 <= 2 x 2! 을 만족하기 때문에 2 로 시작하는 [1, 4] 순열 에 위치할 것이라는 것을 알 수 있다!!
        • ✔ “16번째 순열의 두 번째”는 무조건 2가 된다는 것을 확인할 수 있다. 4번째가 2로 시작하는 순열인 3번째~4번째에 속하기 때문이다. 이제 [3, 2]은 확정됐으니 남은 [1,4] 순열 내에서 4 - 2 = 2 번째에 해당하는 순열을 찾으면 된다.
          • [1,4] 순열 순서의 규칙 (총 2 * 1! = 2개) 📢 [1,4] 순열 내에서 2 번째 찾기
            • 1! = 1개 👉 1 로 시작하는 [4] 순열 👉 1 (=1x1!) 번째
            • 1! = 1개 👉 4 로 시작하는 [1] 순열 👉 2 (=2x1!) 번째
          • 2번째 순열은 1 x 1! < 2 <= 2 x 1! 을 만족하기 때문에 4 로 시작하는 [1] 순열 에 위치할 것이라는 것을 알 수 있다!!
            • ✔ “16번째 순열의 세 번째”는 무조건 4가 된다는 것을 확인할 수 있다. 2번째가 4로 시작하는 순열인 2번째가 되기 때문이다. 이제 [3, 2, 4]은 확정됐으니 남은 [1] 순열 내에서 2 - 2 = 0 번째에 해당하는 순열을 찾으면 된다.
              • ✔ “16번째 순열의 마지막 네 번째”는 무조건 1이 된다는 것을 확인할 수 있다. 하나밖에 안 남았기 때문이다. 남은 순열이 [1] 하나 남았기 때문에 나머지 1을 붙여서 [3, 2, 4, 1] 가 완성된다. 이게 바로 16 번째 순열이 된다.

위 규칙을 아래 코드로 작성했다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

long long perm(int n) // n! 값 구하기
{
    if (n == 0) return 1;
    return n * perm(n - 1);
}

void func(vector<int>& v, vector<int>& answer, long long& k)
{
    if (v.size() == 1) {
        answer.push_back(v[0]);
        return;
    }

    long long p = perm(v.size() - 1); 
    for (int i = 1; i <= v.size(); ++i) {
        if (i * p >= k) {
            answer.push_back(v[i - 1]); // i번째기 때문에 인덱스론 i-1
            v.erase(v.begin() + i - 1);
            k = k - (i - 1) * p;
            func(v, answer, k);
        }
    }
}

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

    vector<int> v(n);
    for (int i = 0; i < n; ++i)
        v[i] = i + 1;  // n=4의 경우 v = [1,2,3,4] 에서 시작

    func(v, answer, k);

    return answer;
}

• func 함수의 재귀 호출 과정을 위의 n = 4, k = 16 을 예로 설명해본다면
  • v는 [1, 2, 3, 4] 👉 [1, 2, 4] 👉 [1, 4] 👉 [1] 로 변해갈 것이다. 이 v의 사이즈가 1이 되었을 때 남은 하나를 answer에 추가하고 재귀를 종료한다.
    • 이에 따라 p는 3! 👉 2! 👉 1!
  • answer는 [3] 👉 [3, 2] 👉 [3, 2, 4] 👉 [3, 2, 4, 1]로 변해갈 것이다.
  • k는 16 👉 12 👉 4 👉 2 👉 0
• 매 재귀마다 if (i * p >= k) 조건을 통해, 현재의 k가 어떤 숫자로 시작하는 순열에 해당하는지 찾아낸다.

O(n!) 에서 O(n^2) 정도로 시간 복잡도가 확 줄어들었다.

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기