[백준] 다음 순열 / JavaScript / node.js

문제

---

https://www.acmicpc.net/problem/10972

10972번: 다음 순열

 

코드

---

• 처음 시도한 풀이 (메모리 초과)

  const fs = require("fs");
  const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
  let input = fs.readFileSync(filePath).toString().trim().split("\r\n");
  
  //순열
  function getPermutation(arr, selectNumber) {
    const result = [];
    if (selectNumber === 1) return arr.map((value) => [value]);
  
    arr.forEach((fixed, index, origin) => {
      const rest = [...origin.slice(0, index), ...origin.slice(index + 1)];
      const permutations = getPermutation(rest, selectNumber - 1);
      const attached = permutations.map((permutation) => [fixed, ...permutation]);
  
      result.push(...attached);
    });
  
    return result;
  }
  
  let prev = input[1]; //찾아야 하는 다음 순열의 이전 순열 (문제에서 주어지는 입력값 순열)
  let numbers = []; //1-N까지의 수를 담을 배열
  for (let i = 1; i <= parseInt(input[0]); i++) numbers.push(i);
  let permutation = getPermutation(numbers, numbers.length); //모든 순열 구하기
  for (let i = 0; i < permutation.length; i++)
    permutation[i] = permutation[i].join(" ");
  
  const prevIndex = permutation.indexOf(prev); //모든 순열에서 prev의 index
  if (prevIndex === permutation.length - 1) console.log(-1);
  else console.log(permutation[prevIndex + 1]);​

• 다시 시도한 풀이 (성공)

  //실버3 다음 순열
  const fs = require("fs");
  const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
  let input = fs.readFileSync(filePath).toString().trim().split("\r\n");
  
  const N = Number(input[0]);
  let numbers = [];
  for (let i = 1; i <= N; i++) numbers.push(i); //1~N까지의 수를 numbers에 담기
  let prev = input[1].split(" ").map((i) => Number(i)); //입력으로 받는 순열을 number화 하여 prev 배열에 저장
  
  let sortNumbers = [...numbers].sort((a, b) => b - a); //numbers배열 내림차순 정렬
  //prev배열이 내림차순돼있다면 순열의 가장 마지막 조합이므로 -1 출력
  if (prev.every((num, index) => num === sortNumbers[index])) console.log(-1);
  else {
    //배열의 맨 뒤에서부터 오름차순이 깨지는 순간의 index (i) 구하기
    let i = N - 2;
    while (prev[i] > prev[i + 1]) i--;
  
    //prev[i] 뒤의 수 중에서 prev[i]보다 큰 수 중에서 가장 작은 값을 가지는 index (j) 구하기
    let j = N - 1;
    while (prev[i] > prev[j]) j--;
  
    //prev[i]와 prev[j] swap하기
    [prev[i], prev[j]] = [prev[j], prev[i]];
  
    let rest = prev.slice(i + 1); //prev[i] 뒤의 값들만 가지는 rest 배열 만들기
    rest.sort((a, b) => a - b); //prev[i] 뒤의 값들은 오름차순 정렬
    let answer = [...prev.slice(0, i + 1), ...rest]; //떼놨던 prev[i]까지의 수와 rest합치기
    console.log(answer.join(" "));
  }​

 

후기

---

• 내가 처음 시도한 풀이는 완전 탐색으로 순열을 찾는 것이었는데, 이 문제는 N의 범위가 10000이나 되기때문에 완전탐색으로 풀면 안되는 것이었다. 당당하게 백준에서 '메모리 초과' 결과를 맞고는 다른 분들의 풀이를 보니 대부분이 규칙을 찾아서 풀이를 하였다.
• 규칙(수도코드로 나타내기)
  
  • if) 배열의 원소들이 내림차순으로 정렬되어 있다면 순열의 마지막 요소란 의미이므로 바로 -1 출력
  • else)
    • 1. 배열의 뒤에서부터 오름차순이 깨지는 순간의 index를 구한다. (i)
    • 2. arr[i]뒤의 수들 중에서 arr[i]보다 큰 수 중에서 가장 작은 값을 가지는 index를 구한다. (j)
    • 3. arr[i], arr[j]의 값을 swap한다.
    • 4. swap해서 바뀐 새로운 arr[i]의 뒤의 값들을 오름차순 정렬한다.
• 규칙을 글로만 봤을 때는 이해가 안됐지만 과정을 하나하나 써가면서 이해하니 쉬운 규칙이었다. 
• 순열 문제라고 해서 꼭 완전탐색할 필요 없이, 규칙을 찾아서 문제를 푸는 방법도 있다는 것을 알게 되었다. 
• 또한, 이 문제를 풀면서 자바스크립트에서는 swap을 할 때, call by value가 적용이 안된다는 것을 알게 되었다. https://lamarr.dev/javascript/2020/04/08/04.html 해당 내용은 이 블로그를 통해 공부했다.
• 나는 원래 swap을 수행하기 위해 swap함수를 만들어 arr[i], arr[j] 값을 인자로 전달했는데, 값이 변하지 않았고, 내가 원하는대로 하기 위해서는 인자로 데이터를 주는 것이 아닌 객체를 전달했어야 한다는 것을 알게 되었다.
• 또 자바스크립트에서는 우리가 흔히 아는 temp를 이용한 swap 말고도 [a, b] = [b, a] 이 한 줄 코드로 아주 쉽게 swap을 수행할 수 있었다.
  

  ---

잘못된 내용이나 수정이 필요한 내용이 있으면 언제든 댓글 달아주세요 감사합니다 😀