[백준] 10972 다음 순열 node.js

문제 링크

10972번: 다음 순열

 

문제 유형

브루트포스 - 순열

 

문제 풀이

• 처음에 모든 순열을 차례로 다 구해서 나열하여 입력값의 순열의 다음 순열을 찾는 방식을 생각했다.
  그러나, 순열은 최대 10,000개의 연속된 수로 있기에 시간초과가 날 것 같아서 다른 방법을 찾아야했다.
• 방법이 생각나지 않아 검색을 했다.
  C++에는 algorithm 헤더 파일을 넣고, 헤더 파일 내의 next_permutation 함수를 사용하면 현재 순열의 다음 순열을 구할 수 있다고 한다. 
• JS에는 이런 내장 함수가 없기에, 직접 구현하여야 한다.

1. 입력값으로 들어온 순열이 사전순으로 마지막에 오는 순열이면(즉, 내림차순으로 정렬된 순열) -1을 반환한다.
2. 순열 배열의 마지막 요소부터 탐색하여 오름차순이 끊기는 시점의 인덱스를 찾고, 변수 a에 저장한다.
3. 오름차순이 끊기는 시점의 값보다 크고, (a + 1) ~ (N - 1) 인덱스 사이인 값들 중 최솟값의 인덱스를 찾아, 변수 b에 저장한다.
4. a 와 b 인덱스에 해당하는 값을 서로 교환한다.
5. 0 ~ a 인덱스의 값과 (a + 1) ~ (N - 1) 인덱스의 값들을 붙인 것이 다음 순열이 된다.

 

코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const input = fs.readFileSync(filePath).toString().trim().split("\n");
const N = Number(input[0]);
const arr = input[1].split(" ").map((v) => +v);

console.log(solution(arr, N));

function solution(arr, N) {
  // 예외처리
  // 얕은 복사를 해서 정렬. 정렬은 원래 배열 자체를 정렬시키기 때문에!
  const descendingSort = [...arr].sort((a, b) => b - a);
  if (arr.every((v, i) => v === descendingSort[i])) return -1;
  else {
    let a = -1; // swap할 요소의 인덱스

    // 배열의 맨뒤부터 시작하여 뒤에서부터 오름차순이 끊기는 시점의 인덱스를 구한다.
    for (let i = N - 1; i > 0; i--) {
      if (arr[i] > arr[i - 1]) {
        a = i - 1;
        break;
      }
    }

    let b = a + 1; // 끊긴시점 전까지의 배열내에서 가장 작은 수의 인덱스, a와 swap한다.
    let min = arr[a + 1];
    for (let i = a + 2; i < arr.length; i++) {
      if (arr[i] < min && arr[i] > arr[a]) {
        // arr[a]보다 큰 끊긴시점 전까지의 배열 중 가장 작은 값을 찾는다.
        min = arr[i];
        b = i;
      }
    }
    [arr[a], arr[b]] = [arr[b], arr[a]]; // arr[a]와 arr[b]를 교체한다.

    return [
      ...arr.slice(0, a + 1),
      ...arr.slice(a + 1).sort((a, b) => a - b),
    ].join(" ");
  }
}

 

참고

https://amunre21.github.io/boj/1-10972/

https://lhoiktiv.tistory.com/447