[백준/JS] 2529 부등호

문제링크: https://www.acmicpc.net/problem/2529

2529번: 부등호

 

완전탐색 + 순열을 사용해서 푼 문제이다.

 

1. DFS로 0 부터 N+1 까지의 순열을 만든다.

2. 재귀의 deps 가 N+1 이 되면 만들어진 순열의 값들이 부등호의 조건을 만족하는지 체크한다.

 

const fs = require('fs');

BOJkey = false;

let input = fs
  .readFileSync(BOJkey ? './javascript/2529/input.txt' : './dev/stdin')
  .toString()
  .trim()
  .split('\n')
  .reverse();

const N = Number(input.pop());
const inequalitySign = input.pop().split(' ');
const temp = [];
const visited = Array.from({ length: 10 }, () => false);
const expactAnswer = [];

const dfs = L => {
  if (L === N + 1) {
    for (let i = 0; i < N; i++) {
      const target = inequalitySign[i];
      switch (target) {
        case '<':
          if (temp[i] > temp[i + 1]) return;
          break;
        case '>':
          if (temp[i] < temp[i + 1]) return;
          break;
      }
    }
    expactAnswer.push(Number(temp.join('')));
  }

  for (let i = 0; i < 10; i++) {
    if (!visited[i]) {
      visited[i] = true;
      temp.push(i);
      dfs(L + 1);
      temp.pop();
      visited[i] = false;
    }
  }
};

dfs(0);

expactAnswer.sort((a, b) => a - b);

console.log(expactAnswer.at(-1));
console.log(expactAnswer[0].toString().padStart(N + 1, '0'));

 

한없이 작아지는 나란 남자

재귀 앞에만 서면 나란남자 시간복잡도를 못 정의하겠다.

그래서 머리를 박아보았다.

 

const dfs = L => {
  if (L > N) {
    return;
  }

  for (let i = 0; i < 10; i++) {
    count++;
    dfs(L + 1);
  }
};

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

 위 함수를 돌려서 몇번 도는가 확인을 해봤더니 10^(N+1) 의 시간복잡도를 얻을 수 있었다. 

 

또한 방문처리가 될때는 얼만큼의 시간복잡도를 가지는지 확인도 해보았다.

const dfs = L => {
  if (L > N) {
    return;
  }

  for (let i = 0; i < 10; i++) {
    count++;
    
    if (visited[i]) continue;
    visited[i] = true;
    temp.push(i);
    dfs(L + 1);
    temp.pop();
    visited[i] = false;
  }
};

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

위 코드를 돌려보면 N = 9 인 경우 10 + 10² + (10!/8! + 10!/7! + 10!/6! + 10!/5! + 10!/4! + 10!/3! + 10!/2! + 10!/1! ) * 10 의 시간 복잡도를 가지게 된다.
딱 봐도 너무 복잡하니 약 K! * (N+1)  의 시간 복잡도를 갖는다고 생각하면 될 것 같다. 따라서 O(K! * N) 이 된다.

여담으로 재귀를 사용해 구현한 조합의 경우 O(2^n)의 시간복잡도를 가진다.