Goni's dev_log

문제

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

코드

//실버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 next = input[1].split(" ").map((i) => Number(i)); //입력으로 받는 순열을 number화 하여 next 배열에 저장

let sortNumbers = [...numbers].sort((a, b) => a - b); //numbers배열 오름차순 정렬
//next배열이 오름차순돼있다면 순열의 가장 처음 조합이므로 -1 출력
if (next.every((num, index) => num === sortNumbers[index])) console.log(-1);
else {
  //배열의 맨 뒤에서부터 내림차순이 깨지는 순간의 index (i) 구하기
  let i = N - 2;
  while (next[i] < next[i + 1]) i--;

  //next[i] 뒤의 수 중에서 next[i]보다 작은 수 중에서 가장 큰 값을 가지는 index (j) 구하기
  let j = N - 1;
  while (next[i] < next[j]) j--;

  //next[i]와 next[j] swap하기
  [next[i], next[j]] = [next[j], next[i]];

  let rest = next.slice(i + 1); //next[i] 뒤의 값들만 가지는 rest 배열 만들기
  rest.sort((a, b) => b - a); //next[i] 뒤의 값들은 내림차순 정렬
  let answer = [...next.slice(0, i + 1), ...rest]; //떼놨던 next[i]까지의 수와 rest합치기
  console.log(answer.join(" "));
}

후기

• '다음 순열(10972번)'문제와 쌍둥이 문제이기 때문에 '다음 순열' 문제를 풀었다면 쉽게 규칙을 찾아 풀 수 있을 것이다.
• '다음 순열' 풀이는 https://king-goni.tistory.com/entry/%EB%B0%B1%EC%A4%80-%EB%8B%A4%EC%9D%8C-%EC%88%9C%EC%97%B4-JavaScript-nodejs << 여기를 참고하면 된다! 

  ---

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

문제

https://www.acmicpc.net/problem/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을 수행할 수 있었다.
  

  ---

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

문제

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

코드

//실버3 모든 순열
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\r\n");

//순열
// arr : 수가 담겨 있는 배열
// selectNumber : 몇개로 구성된 순열을 구할 것인가
function getPermutation(arr, selectNumber) {
  const result = []; //결과를 담을 배열
  if (selectNumber === 1) return arr.map((value) => [value]); //1개로 구성된 순열에 대해서는 바로 배열에 담기

  //arr의 각 수에 대해
  arr.forEach((fixed, index, origin) => {
    const rest = [...origin.slice(0, index), ...origin.slice(index + 1)]; //fixed(고정값)를 제외한 배열을 rest에 담기
    const permutations = getPermutation(rest, selectNumber - 1); //rest에서 고정값을 제외한 개수(selectNumber-1 개)의 순열을 재귀로 구하기
    const attached = permutations.map((permutation) => [fixed, ...permutation]); //재귀를 통해 만들어진 순열에 고정값이었던 fixed를 붙이기

    result.push(...attached);
  });

  return result;
}

let numbers = [];
for (let i = 1; i <= parseInt(input[0]); i++) numbers.push(i); //1~N 까지의 수를 numbers에 담음
let answer = getPermutation(numbers, numbers.length); //순열함수의 결과를 answer에 담음
for (let i = 0; i < answer.length; i++) {
  console.log(answer[i].join(" "));
}

후기

• 프로그래머스의 '소수 찾기(완전탐색)' 문제처럼 순열을 연습하는 문제였는데, 두 문제의 차이점은 '소수 찾기'는 배열내의 숫자로 만들 수 있는 모든 개수의 순열을 찾는 것이고, 이 문제는 내가 지정하는 개수로 구성된 순열을 찾는 것이다. 그래서 그런지 두 문제의 풀이가 좀 달라서 두 풀이의 차이점을 분석해 봐야겠다. 

  ---

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

문제

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

코드

//실버5 소트인사이드
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\r\n");

input = input
  .shift()
  .split("")
  .sort((a, b) => b - a);
console.log(input.join(""));

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