알고리즘
[백준] 10972 다음 순열 node.js
sandwe
2022. 7. 2. 01:35
문제 링크
10972번: 다음 순열
첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다.
www.acmicpc.net
문제 유형
브루트포스 - 순열
문제 풀이
- 처음에 모든 순열을 차례로 다 구해서 나열하여 입력값의 순열의 다음 순열을 찾는 방식을 생각했다.
그러나, 순열은 최대 10,000개의 연속된 수로 있기에 시간초과가 날 것 같아서 다른 방법을 찾아야했다. - 방법이 생각나지 않아 검색을 했다.
C++에는 algorithm 헤더 파일을 넣고, 헤더 파일 내의 next_permutation 함수를 사용하면 현재 순열의 다음 순열을 구할 수 있다고 한다. - JS에는 이런 내장 함수가 없기에, 직접 구현하여야 한다.
- 입력값으로 들어온 순열이 사전순으로 마지막에 오는 순열이면(즉, 내림차순으로 정렬된 순열) -1을 반환한다.
- 순열 배열의 마지막 요소부터 탐색하여 오름차순이 끊기는 시점의 인덱스를 찾고, 변수 a에 저장한다.
- 오름차순이 끊기는 시점의 값보다 크고, (a + 1) ~ (N - 1) 인덱스 사이인 값들 중 최솟값의 인덱스를 찾아, 변수 b에 저장한다.
- a 와 b 인덱스에 해당하는 값을 서로 교환한다.
- 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(" ");
}
}