[순열] 백준 : 다음 순열, 이전 순열, 모든 순열

다음 순열 : https://www.acmicpc.net/problem/10972

이전 순열 : https://www.acmicpc.net/problem/10973

모든 순열 : https://www.acmicpc.net/problem/10974

 

 

다음 순열과 이전 순열에선 우선 input으로 어떤 수열이 주어진다.그러면 결과로 그 수열 이후/이전에 오는 순열(permutation)을 프린트한다.

 

모든 순열에선 n이 주어지며, 1 ~ n 까지 모든 permutation을 구하면 된다.

 

 

---

1. 반복문으로 해결하기 - 다음 순열

 

next_permutation이 치트키이지만... 안쓰고 반복문으로 도전해보았다.

 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int N, k;

void printNum(vector<int> nums)
{
  for (auto num : nums)
    cout << num << ' ';
  cout << '\n';
}

int main(void)
{
  cin >> N;
  vector<int> numbers;

  for (int i = 0; N > i; i++)
  {
    cin >> k;
    numbers.push_back(k);
  }

  if (N == 1)
  {
    cout << -1 << '\n';
    return 0;
  }

  int lastNum = N - 1; // i의 바로 오른쪽에 있는 숫자.

  for (int i = N - 1; i >= 0; i--) // 맨 오른쪽에서부터 왼쪽으로 탐색을 시작한다.
  {
    if (numbers[lastNum] > numbers[i]) // 오른쪽에서 왼쪽으로 탐색을 하다가, 숫자가 감소하는 지점에 도달시
    {
      int nextIdx = N - 1;
      for (; numbers[nextIdx] < numbers[i]; nextIdx--) // numbers[i]의 오른쪽에서, numbers[i] 보다 더 큰 첫번째 수를 찾음
        ;

      iter_swap(numbers.begin() + i, numbers.begin() + nextIdx); // 그리고 그 수를 numbers[i] 와 스왑.
      sort(numbers.begin() + lastNum, numbers.end());            // i의 바로 오른쪽에 있는 숫자부터 끝까지 오름차순 정렬.
      printNum(numbers);
      return 0;
    }

    if (numbers[lastNum] <= numbers[i]) lastNum = i; // 오른쪽에서 왼쪽으로 갈수록 숫자가 증가하면, lastNum을 한칸씩 왼쪽으로 옮김.
  }

  cout << -1 << '\n';
  return 0;
}

 

아이디어는 다음과 같다.

주어진 순열의 오른쪽에서부터 왼쪽으로 탐색하는데, 숫자가 커지면 패스하고 작아지는 지점에서 멈춘다. 그리고 그 지점까지, 지점보다 큰 첫번째 수를 찾아 지점과 스왑한다. 이후, 원래 지점의 자리 바로 오른쪽에서부터 끝까지 오름차순 정렬을 하면 끝!

(쉽지만은 않았다..ㅎㅎㅎ)

 

 

---

 

2. next_permutation, prev_permutation 을 사용하여 해결하기 - 이전 순열

 

치트키를 써보았다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(void)
{
  int N, k;
  vector<int> nums;

  cin >> N;

  for (int i = 0; N > i; i++)
  {
    cin >> k;
    nums.push_back(k);
  }

  if (prev_permutation(nums.begin(), nums.end()))
  {
    for (auto num : nums)
      cout << num << ' ';
    cout << '\n';
    return 0;
  }

  cout << -1 << '\n';
  return 0;
}

 

코드가 훨씬 깔끔하고 직관적이다!

next_permutation과 prev_permutation은 다음/이전 순열 생성시 true을 반환한다. 생성에 실패할 경우 false를 반환한다. next_permutation/prev_permutation 함수 호출시, nums는 다음/이전 순열로 바뀐다.

 

 

 

---

 

3. 모든 순열

 

기본적인 순열 생성 문제.

 

#include <iostream>
#include <vector>

using namespace std;

int N, numStatus[8] = {0};

void permutation(vector<int> nums)
{
  if (nums.size() == N)
  {
    for (auto num : nums)
      cout << num << ' ';
    cout << '\n';
    return;
  }

  for (int i = 0; N > i; i++)
  {
    if (numStatus[i])
      continue;
    nums.push_back(i + 1);
    numStatus[i] = 1;

    permutation(nums);

    nums.pop_back();
    numStatus[i] = 0;
  }
}

int main(void)
{
  cin >> N;
  vector<int> nums;

  permutation(nums);

  return 0;
}