[백준 10972] 다음 순열 with Node.js

문제 링크

https://www.acmicpc.net/problem/10972

10972번: 다음 순열

풀이

const [ N, ...arr ] = require('fs').readFileSync('/dev/stdin').toString().trim().split(/\s+/).map(v => +v);

const solve = (N, arr) => {
  const arrCopy = [...arr].sort((a, b) => b - a);
  if (arr.every((v, i) => v === arrCopy[i])) {
    console.log(-1);
  } else {
    let i = N - 2;
    while (arr[i] > arr[i+1]) {
      i--;
    }
    let j = N - 1;
    while (arr[i] > arr[j]) {
      j--;
    }
    [ arr[i], arr[j] ] = [ arr[j], arr[i] ];
    console.log([...arr.slice(0, i+1), ...arr.slice(i+1).sort((a, b) => a - b)].join(' '));
  }
};

solve(N, arr);

N의 최댓값이 10000이나 되기 때문에 모든 경우를 다 탐색할 수 없고, 다음 순열이 어떤 순서인지 규칙을 찾아서 풀었다.

 

내림차순으로 정렬이 되어 있는 상태는 마지막 순열이므로, -1을 출력한다.

 

그 외의 경우, 규칙에 따라 다음 순열을 만들어서 출력한다.

 

예를 들어, 1 3 5 4 2의 다음 순열을 구한다고 하자.

뒤에서부터 2 4 5까지는 오름차순인데, 3에서 2 4 5 3이 되어 오름차순이 깨진다.

이렇게 뒤에서부터 오름차순이 깨지는 숫자의 인덱스 i를 구한다.

 

arr[i] 뒤에 있는 수들 중에서 arr[i]보다 큰 가장 작은 값을 가지는 숫자의 인덱스 j를 구한다.

1 3 5 4 2에서 3 뒤에 있는 5 4 2 중에서 3보다 큰 수들 5 4 중에 가장 작은 값은 4다.

 

이렇게 구한 arr[i]와 arr[j]의 자리를 서로 바꾼다.

1 3 5 4 2 => 1 4 5 3 2

 

그 다음, i번째 수 뒤에 있는 5 3 2를 오름차순으로 정렬하면 다음 순열이 된다.

1 4 5 3 2 => 1 4 2 3 5