백준 10973번: 이전 순열 - javascript

백준 10973번: 이전 순열

문제 설명

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

접근

백준 10972번이 다음 순열을 찾는 문제였다면, 이번 문제는 거꾸로 이전 순열을 찾는 문제다.

방법은 그냥 다음 순열에서 순열 찾는 조건만 바꿔주면된다.
뒤에서 부터 오름차순을 찾는 것이 아니라 뒤에서 부터 내림차순을 찾다가 오름차순이 되는 순간을 끊는 시점으로 바꾸면된다.

실행과정은 다음과 같다.

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

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

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

temp = [2, 4];

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

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

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

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

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

남은 temp = [3, 4]

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

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

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

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

이렇게 이전순열과 다음순열을 풀어보면서 이제 순열구하는 문제는 확실하게 알 것 같다.

정답 코드

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 = brute(n,m);
  console.log(answer)
  process.exit();
});

let brute = function(n,m){
  let tmp = [];
  let broke = -1;
  let min = 10001;
  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(' '));
}