[백준] 10972 다음 순열 JavaScript

혅·2024년 6월 28일

JavaScript

백준, 프로그래머스 -JavaScript-

목록 보기

109/215

문제

1부터 N까지의 수로 이루어진 순열이 있다. 이때, 사전순으로 다음에 오는 순열을 구하는 프로그램을 작성하시오.

사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다.

N = 3인 경우에 사전순으로 순열을 나열하면 다음과 같다.

1, 2, 3
1, 3, 2
2, 1, 3
2, 3, 1
3, 1, 2
3, 2, 1

입력

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

출력

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

예제 입력

4
1 2 3 4

예제 출력

1 2 4 3

내가 했던 풀이 방법

sequence를 내림차순으로 정렬했을 때 입력받은 sequence와 같다면 -1을 출력한다.
1번이 아닌 경우, N-2부터 현재 요소와 다음 요소가 내림차순으로 진행되지 않는 첫 부분을 찾는다. 예를 들어, 1 3 4 2라고 할 때, 4 2까지는 내림차순으로 진행되지만 3부터는 내림차순이 진행되지 않기 때문에 3이 위치한 index를 i에 저장한다. N-1부터 현재 요소가 이전에서 찾은 값 (내림차순이 진행되지 않게 된 수)보다 큰 수가 나올 때까지 찾고 해당 index를 j에 저장한다.
i와 j의 위치한 값을 swap해준다.
answer 배열에 i까지의 값을 slice 해준다. tail 배열에는 i+1부터 끝까지의 값을 slice 해준다.
tail 배열을 오름차순으로 정렬해준 다음 answer에 합쳐준다.
answer를 출력한다.

코드

const fs = require('fs');
let [N, sequence] = fs.readFileSync(0, 'utf-8').toString().trim().split('\n');

N = Number(N);
sequence = sequence.trim().split(' ').map(Number);

let sort = [...sequence].sort((a, b) => b - a);
let answer = [];
let tail = [];
if (sequence.every((value, index) => value === sort[index])) {
  console.log(-1);
} else {
  let i = N - 2;
  while (sequence[i] > sequence[i + 1]) i--;
  let j = N - 1;
  while (sequence[i] > sequence[j]) j--;
  [sequence[i], sequence[j]] = [sequence[j], sequence[i]];
  answer = sequence.slice(0, i + 1);
  tail = sequence.slice(i + 1).sort((a, b) => a - b);
  answer = answer.concat(tail);
  console.log(answer.join(' '));
}