백준 10972번: 다음 순열 - javascript

백준 10972번: 다음 순열

문제 설명

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을 출력한다.

접근

백준 N과M시리즈가 생각나는 문제다.
그런데 그 문제는 N의 범위가 작은데 비해서 이번문제는 무려 10,000까지 주어진다.
그 말은 그냥 반복문으로는 원하는 순열을 못 구한다는 뜻이다.
그것도 모르고 나는 반복문으로 돌려서 첫 채점을 런타임 에러를 받았다

런타임 에러를 겪고 나서야 보이는 N의 범위, 이제 저걸 어떻게 해결하지?
만약 당신이 자바나 자바스크립트 등이 아닌 C++을 쓰고있다면 algorithm 헤더에서 next_permutation을 가져다가 사용하면 된다!… 그래서 코테는 c++로 보라하는구나

하지만 나는 자바스크립트, 고로 next_permutation을 구현해야한다.
먼저 특정한 순열에 대해 다음 순열 값을 알아내는 방법부터 알아야 한다.
다음순열을 구하는 방법은 아래와 같다.

순열	2	1	5	4	3
오름차순 체크		X	5	4	3

• 맨 뒤에서부터 시작해서 오름차순이 끊기는 시점을 찾는다.

순열	2	1	5	4	3
오름차순 체크		X

temp = [5,4,3];

• 끊긴 시점 이전까지의 수 들을 저장한다.
• 끊긴 시점의 수를 본다.

순열	2	1	5	4	3
오름차순 체크		X
바꾼순열	2

temp = [5,4,3]에서
1보다 큰 수 中 제일 작은 수 => 3

• 2번에서 저장한 수들 중에서 끊긴 다음 시점의 수보다 바로 한단계 큰 수를 찾는다.

순열	2	1	5	4	3
내림차순 체크		X
바꾼순열	2	3

남은 temp = [5,4,1]

• 끊긴 시점의 수를 해당 수로 교체한다.

순열	2	1	5	4	3
바꾼순열	2	3	1	4	5

• 남은숫자들을 오름차순 정렬해서 다시 붙여준다.

이런식으로 과정이 이루어진다.
이걸 코드로 바꾸면 이렇게 된다.

주어진 순열을 배열로 바꾸고, 주어진 n-1부터 0까지 내려가면서 오름차순이 끊길 때까지 배열에 값들을 넣는다.
이때 push를 이용해서 넣는다면 오름차순이 그대로 들어갈테니 이따가 순열을 합성 할 때 편하다
오름차순이 끊기는 순간의 index값을 저장하고 반복문을 종료한다.
이번에는 오름차순 값들을 저장한 배열을 0부터 배열의 길이 만큼 반복문을 돌리면서 오름차순이 끊긴 index의 자연수 값보다 배열의 인덱스 값이 크게 나오는 순간까지 돌린다.
큰 값이 나오게 되면 해당 값과 인덱스값을 서로 바꿔준다.

기존 순열은 끊긴 index까지 슬라이스하고 뒷 부분은 오름차순을 저장한 배열을 붙여주고 반환해준다.
(그런데 맨처음에 반복문이 아니라 pop을 이용해서 while문으로 돌리면 더 깔끔해 질 것 같긴하다.)

정답 코드

const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});
let input = [];
rl.on('line', function (line) {
  input.push(line);
})
  .on('close', async function () {
  // 답안 작성
  let answer =0;    
  let n = input[0];
  let m = input[1];
  answer = next_permutation(n,m);
  console.log(answer)
  process.exit();
});

let next_permutation = function(n,m){
  let tmp = [];
  let broke = -1;
  let min = -1;
  m = m.split(' ');
  for(let i=n-1;i>=0;i--){
    if(min*1>m[i]*1){
      broke = i;
      break;
    }
    tmp.push(m[i]);
    min = m[i]*1;
  }  
  if(broke == -1)return -1;
  for(let i =0;i<tmp.length;i++){
    if(m[broke]*1<tmp[i]*1){
      let change = tmp.splice(i,1,m[broke]);
      m[broke] = change.join('');
      break;
    }
  }  
  return (m.slice(0,broke+1).join(' ') +' '+ tmp.join(' '));
}