백준 10972 다음 순열

문제

제한 사항

입력
첫째 줄에 N(1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄에 순열이 주어진다.

출력
첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다.

입출력 예

예제 입력 1
4
1 2 3 4
예제 출력 1
1 2 4 3

예제 입력 2
5
5 4 3 2 1
예제 출력 2
-1

풀이

let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
let n = +input.shift();
let target = input.shift();

const solution = (n, target) => {
  let answer;
  const arr = target.split(" ").map((e) => +e);
  const arrCopy = [...arr].sort((a, b) => b - a);
  if (arr.every((e, i) => e === arrCopy[i])) {
    return -1;
  } else {
    let i = n - 2; // arr.length -2
    // 마지막이 가장 클 수 있으니 이런식으로 비교하는게 맞음.
    while (arr[i] > arr[i + 1]) {
      i--;
    }
    
    let j = n - 1; // arr.length -1, 뒤부터 비교
    while (arr[i] > arr[j]) {
      j--;
    }
    [arr[i], arr[j]] = [arr[j], arr[i]];
    answer = [
      ...arr.slice(0, i + 1),
      ...arr.slice(i + 1, n).sort((a, b) => a - b),
    ].join(" ");
  }
  return answer;
};

console.log(solution(n, target));

• 입력이 최대 10,000이라 백트래킹(재귀)로는 풀 수 없다.
• 규칙을 알아내 이용해서 풀어야한다.
• 문자를 뒤에서부터 탐색하며 오름차순이 끝나는 인덱스를 찾는다.
• 그리고 그 문자보다 큰 값 중 작은 값을 다시 뒤에서부터 찾은 다음 교환해준다.
• 그리고 찾은 인덱스 뒤에 부분은 정렬해주면 다음 수가 나온다.
• 13542로 예를 들면, 오름차순이 끝나는 수는 3, 3 이후로 큰 값중 작은 값은 4임으로 교환해서 14532이고 4 이후로 정렬하면 14235가 된다.

const solution = (n, target) => {
  let answer;
  const arr = target.split(" ").map((e) => +e);
  const arrCopy = [...arr].sort((a, b) => b - a);
  if (arr.every((e, i) => e === arrCopy[i])) {
    return -1;
  } else {
    let i = n - 1;
    while (arr[i] < arr[i - 1]) {
      i--; // 뒤에서 부터 오름차순이 끊어지는 i 값
    }
    if (i === n - 1) {
      i--; 
      // i값이 초기값과 비교했을 때 변하지 않았다면 arr 배열은 현재 뒤에서부터 내림차순인 배열인 것(앞으로치면 오름차순) arr[i]가 최대값이기 때문에 교환을 위해 -1을 해준다.
    }
    let j = n - 1;
    while (arr[i] > arr[j]) {
      j--;
      // 뒤에서 부터 arr[i] 보다 큰 값의 index를 찾는다.
    }

    [arr[i], arr[j]] = [arr[j], arr[i]]; // 그 둘을 교환
    answer = [
      ...arr.slice(0, i + 1),
      ...arr.slice(i + 1, n).sort((a, b) => a - b),
    ].join(" "); // 뒤에는 정렬해서
  }
  return answer;
};

console.log(solution(4, "1 2 3 4"));