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

문제링크

풀이

• 순열의 뒤에서부터 오름차순이 끊기는 곳을 찾고 (편의상 끊기는 곳을 idx라 하자)

• 해당 idx의 뒤에서 그 값보다 크지만 뒤의 리스트보다 가장 작은 아이를 찾아서

• idx와 순서를 바꾸고

• idx+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]);

let nowList = input[1].split(" ").map(Number);
let isLast = -1;

for (let i = nowList.length - 1; i > 0; i--) { // 뒤에서부터
  if (nowList[i] > nowList[i - 1]) {
    // 오름차순이 끊기면
    isLast = i - 1;
    break;
  }
}

const findSwap = (idx) => {
  let min = 10001;
  let minIdx = 0;
  for (let i = idx; i < n; i++) {
    if (nowList[i] > nowList[idx] && nowList[i] < min) {
      min = nowList[i];
      minIdx = i;
    }
  }
  return minIdx;
};

if (isLast === -1) {
  console.log(isLast);
} else {
  let minIdx = findSwap(isLast);
  [nowList[minIdx], nowList[isLast]] = [nowList[isLast], nowList[minIdx]]; // 바꾸고
  // isLast 뒤부터 정렬
  console.log(
    [
      ...nowList.slice(0, isLast + 1),
      ...nowList.slice(isLast + 1).sort((a, b) => a - b),
    ].join(" ")
  );
}

참고
Blog, [백준 10972] 다음 순열 with Node.js