줄 서는 방법 - 순열 알고리즘

문제

N명의 사람이 있을 때, N명의 사람을 서로 다른 방법으로 줄을 세우는 방법은 N!개가 존재합니다.

이 때 각각의 사람들에게 번호를 매겨서 줄을 서는 방법을 표시합니다. 예를들어 [1,2,3,4]는 1번 사람이 제일 앞에, 2번 사람이 2두번째에 서 있는 상태를 나타냅니다.

이러한 각각의 방법을 사전순으로 정렬했을때 K번째 방법으로 줄을 세우는 방법을 찾아 보려고 합니다.

예를 들어 3명의 사람이 있다면 총 6개의 방법은 다음과 같이 정렬할 수 있습니다.

• 1번째 방법은 [1,2,3]
• 2번째 방법은 [1,3,2]
• 3번째 방법은 [2,1,3]
• 4번째 방법은 [2,3,1]
• 5번째 방법은 [3,1,2]
• 6번째 방법은 [3,2,1]

이 때 K가 5이면 [3,1,2]가 그 방법입니다.

사람의 수 N과 순서 K를 입력받아 K번째 방법으로 줄을 세우는 setAlign 함수를 완성해 보세요. 예를 들어 setAlign(3,5)를 입력받는다면 [3,1,2]를 리턴해주면 됩니다.

풀이

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

vector<int> setAlign(int n, long long cnt)
{
  vector<int> answer, people;
  long long   fec = 1;
  cnt--;

  for (int i = 1; i <= n; i++)
  {
    fec *= i;
    people.push_back(i);
  }

  while (n > 0)
  {
    fec = fec / n--;
    answer.push_back(people.at(cnt / fec));
    people.erase(people.begin() + cnt / fec);
    cnt %= fec;
  }

  return answer;
}
int main()
{
  int         testn      = 3;
  long long   testcnt    = 5;
  vector<int> testAnswer = setAlign(testn, testcnt);
  // 아래는 테스트로 출력해 보기 위한 코드입니다.

  for (int i = 0; i < testAnswer.size(); i++)
  {
    cout << testAnswer[i] << " ";
  }
}

이번 문제 역시 직관적으로 풀면 큰 어려움 없이 풀 수 있다.

그래도 좀 다르게 풀어보고자 시도해본게 위 코드이다.

처음 for문은 그다지 볼 건 없지만 쉽게 말해서 팩토리얼을 만드는 부분과 사람 리스트를 만드는 것이다.

예를 들어 사람이 4명 들어오면 10! 을 구하는 거고 people이란 벡터를 만들어 {1, 2, 3, 4}로 저장하는 부분이다. (그다지 설명이..)

 

중요한건 while 부분인데 people 벡터를 만든 이유는 아래에서 설명하고..

예시로 흐름을 살펴보면

먼저 사람이 줄을 서는 경우는 문제와 같이 n!이다. 이해를 돕기 위해 4명의 사람, 8번째 순서로 가정하면

줄을 세우는 방법은 총 4! (= 24)가지이다. 이는 다시 말해

처음 오는 사람이 1번 사람일 경우 6가지, 2번 사람일 경우 6가지… 4번 사람일 경우 6가지이다.

우리가 구하고자 하는 목표는 순서대로 나열했을 경우 cnt 번째 순서를 구하는 것인데, 이는 다시 말해 처음 나오는 사람의 번호를 구하는 것이다.

먼저 프로그래밍 상 n번째는 보통 인덱스로 n-1을 의미한다. 배열에서 첫 번째 원소 인덱스가 0인 것과 같이…

그래서 ~번째보다 ~인덱스로 사용하기 위해 cnt를 1 감소시켰다.

그럼 1번째부터 6번째까지는 1번 사람이 맨 앞에 올 것이다. 7번째부터 12번째는 당연히 2번 사람이 맨 앞에 올 것이고.. 따라서 인덱스를 기준으로 생각해보면 0~5번 인덱스까지는 1번 사람이 맨 앞에 온다.

그럼 6가지는 어디서 나온 것일까? 이미 감을 잡았겠지만 총 가지수가 4!이므로 4명의 사람에 대한 경우는 3!(=6)이다.

따라서 구하고자 하는 cnt 번째를 알기 위해서는 cnt-1을 6으로 나눈 몫을 알면 된다.

8 – 1을 6으로 나누면 몫이 1이다. 이는 곧 앞서 만들어 두었던 people의 1번 인덱스, people[1] = 2 이므로 2번 사람이 맨 앞에 옴을 뜻한다.

따라서 answer에 2번 사람을 추가하고, 2번 사람을 people에서 삭제한다. 그럼 남은 배열은 {1, 3, 4}가 되고 자연스럽게 인덱스 역시 0, 1, 2로 변경된다.

이제 남은 것은 1, 3, 4사람을 구하는 것인데 위의 방법과 완전히 동일하다. 총 24가지 방법 중 8번째의 방법을 알기 위해 2번째 사람이 맨 앞에 오는 그룹이라는 것을 알았다.

즉 7 / 6의 나머지인 1 번 인덱스(순서로는 2번째이다)라는 것을 알 수 있고 따라서 동일한 방법으로 1 / 2!을 하면 0의 몫과 1의 나머지가 생긴다.

즉 people 배열에서 0번 인덱스에 위치한 1번 사람이 다음 오는 순서임을 알 수 있고 1번 사람을 추가한다.

 

마찬가지로 나머지가 1이므로 1 / 1!을 해주면 마지막 사람까지 알 수 있다.

한번 읽으면 이해가 잘 안될텐데 내용을 손으로 따라 그려보면서 이해하면 될 것 같다. 인덱스를 사용하여 나타낸 이유는 이게 익숙한 것도 있는데 ~번째 라고 하면 내용이 좀 이상해진다.

예를 들어 8 / 6을 해서 몫은 1이 나오는데 나머지가 2가 나온다. 그럼 다음 사람을 구할 때 나머지가 2이므로 2 / 2를 하게 되어 몫이 1이 나오는데 배열에서 첫 번째 사람이라고 생각하면 되지만 그럼 다음 사람은 0 / 1!이므로 0번째 사람이 되고..

아무튼 틀린 방법이라기 보다 그냥 필자가 헷갈려 인덱스를 기준으로 사용하였다. 🙂

출처

알고리즘 연습 Level 5 | 프로그래머스