[백준_10972] 다음 순열 ( 브루트포스 - 자바스크립트 )

문제

 

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

10972번: 다음 순열

 

How to Solve ?

 

[1] 브루트포스

 

1. 주어진 길이의 순열을 백트래킹을 통해 만든다 

function dfs(cnt) {
  if (cnt === n) {
    permuArr.push(output.join(""));
    return;
  }

  for (let i = 1; i <= n; i++) {
    if (visited[i]) continue;

    visited[i] = 1;
    output.push(i);
    dfs(cnt + 1);
    output.pop();
    visited[i] = 0;
  }
}

 

2. 만든 배열을 돈다.

 

만약 찾고자 하는 수가 마지막 위치에 있다면  -1 을 출력하고, 그게 아니라면 다음 값을 출력해준다.

function solve() {
  const index = permuArr.indexOf(target);

  if (index == permuArr.length - 1) {
    return -1;
  } else {
    return permuArr[index + 1].split("").join(" ");
  }
}

 

전체코드

function dfs(cnt) {
  if (cnt === n) {
    permuArr.push(output.join(""));
    return;
  }

  for (let i = 1; i <= n; i++) {
    if (visited[i]) continue;

    visited[i] = 1;
    output.push(i);
    dfs(cnt + 1);
    output.pop();
    visited[i] = 0;
  }
}

function solve() {
  const index = permuArr.indexOf(target);

  if (index == permuArr.length - 1) {
    return -1;
  } else {
    return permuArr[index + 1].split("").join(" ");
  }
}

const n = 4;
const permuArr = [];
const output = [];
const visited = Array(n).fill(0);
const nums = Array.from({ length: n }, (v, i) => i + 1);
const target = "1234";

dfs(0);
console.log(solve());