[백준] 2529번 부등호 - JavaScript(NodeJS)

문제

2529번: 부등호

 

풀이

Brute Force(무차별 대입, 무식하게 풀기?) 문제이다.

 

정수의 개수 k의 범위가 2<=k<=9 이므로
가능한 모든 경우의 수를 탐색해도 충분하다.

 

숫자 사이에는 부등호가 들어가는데, 부등호를 만족시키는 숫자가 배치되면 된다.

 

예를 들면,

1<2<5>4<6 와 같이 부등호를 만족시키는 수 중에서, 모든 부등호를 제거했을 때의 문자를 가지고 최댓값과 최솟값 구한다.

 

간단한 방문 배열을 선언했고
재귀함수에서 부등호에 따라 부등호 앞 숫자보다 크거나 작은 숫자를 순차적으로 선택해서 모두 조회한다.

부등호를 모두 사용했다면, 성공적으로 부등호를 만족하는 숫자 배치를 마친 것.

이 시점에서 숫자의 최대 최소 여부를 판단한다.

 

 

※ 주의사항

예시 정답을 보면 897, 021이 출력된다.

즉 숫자 값을 문자열 형태로 출력해야 한다.

 

자바스크립트에서는 숫자를 담은 문자열끼리도 부등호로 크기 비교가 가능하다.

예를 들어 "15" > "03" = true /  "33" > "53" = false 가 출력된다.

 

이를 이용해서 문자열 형태의 숫자들 간 크기 비교를 통해 최대최소 여부를 판단해보자.

 

코드를 보자.

코드

const sol = (input) => {
  const N = +input[0];
  const inequality = input[1].split(" ");
  const visit = new Array(10).fill(0);
  let max = String(Number.MIN_SAFE_INTEGER); 
  let min = String(Number.MAX_SAFE_INTEGER); // min, max를 문자열 형태로 선언한다.

  function dfs(L, prev, result) {
    if (L === N) { // L=N 이라면 모든 부등호가 사용 된 것
      max = result > max ? result : max;
      min = result < min ? result : min;
      return;
    }
    if (inequality[L] === "<") {
      for (let i = prev + 1; i < 10; i++) { // 부등호가 < 이면 전 숫자보다 큰 숫자에서 사용 가능 여부를 판단
        if (visit[i]) continue;
        visit[i] = 1;
        dfs(L + 1, i, result + i); // result + i 는 문자열이다. 즉, "02" + "1" => "021" 형태.
        visit[i] = 0; // 재귀적으로 visit 배열을 계속 사용해야 하므로 사용 가능 여부를 없애고 재귀가 끝나면 다시 부여한다.
      }
    } else {
      for (let i = prev - 1; i > -1; i--) { // 부등호가 > 이면 전 숫자보다 작은 숫자에서 사용 가능 여부를 판단
        if (visit[i]) continue;
        visit[i] = 1;
        dfs(L + 1, i, result + i);
        visit[i] = 0;
      }
    }
    return;
  }

  for (let i = 0; i < 10; i++) { // 첫 숫자가 0~9까지 모두 조회하면 된다.
    visit[i] = 1;
    dfs(0, i, `${i}`);
    visit[i] = 0;
  }

  return `${max}\n${min}`;
};

// 백준에서 입력을 받는 코드
const input = [];
require("readline")
  .createInterface(process.stdin, process.stdout)
  .on("line", (line) => {
    input.push(line);
  })
  .on("close", () => {
    console.log(sol(input));
    process.exit();
  });