2529.md

부등호

문제

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

정답

다음 문제의 경우 백트래킹으로 풀이하였다.

let [k, arr] = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
  .toString()
  .split("\n");

arr = arr.split(" ");

// 방문한 숫자인지 체크하는 배열
let visited = new Array(10).fill(false);

// 현재 순열의 상태를 저장하는 배열
let result = [];

// 가장 큰 값, 가장 작은 값
let [last, first] = ["", ""];

dfs(0);
console.log(last + "\n" + first);

// 백트래킹
function dfs(depth) {
  // 깊이가 k+1이면 탐색을 종료하고 출력한다.
  if (depth == +k + 1) {
    // 부등호를 만족하는지 체크
    let check = true;
    for (let i = 0; i < +k; i++) {
      if (arr[i] == "<") {
        if (result[i] > result[i + 1]) {
          check = false;
        }
      } else if (arr[i] == ">") {
        if (result[i] < result[i + 1]) {
          check = false;
        }
      }
    }
    // 부등호를 만족하면
    if (check) {
      // 마지막 값이 가장 큰 값
      last = result.join("");
      // 가장 작은 값
      if (first == "") first = last;
    }
    return;
  }
  // 깊이가 k+1이 아니면 0부터 9까지의 숫자를 하나씩 골라서 재귀호출한다.
  // 0부터 9까지의 숫자를 하나씩 고르는 순열
  for (let i = 0; i < 10; i++) {
    if (visited[i]) continue; // 이미 방문한 경우
    visited[i] = true; // 방문 처리
    result.push(i);
    dfs(depth + 1);
    visited[i] = false; // 방문 처리 해제
    result.pop();
  }
}