부등호 (백준 2529번)

문제

두 종류의 부등호 기호 ‘<’와 ‘>’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시된 부등호 순서열 A가 다음과 같다고 하자. 

A ⇒ < < < > < < > < >

부등호 기호 앞뒤에 넣을 수 있는 숫자는 0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다. 아래는 부등호 순서열 A를 만족시키는 한 예이다. 

3 < 4 < 5 < 6 > 1 < 2 < 8 > 7 < 9 > 0

이 상황에서 부등호 기호를 제거한 뒤, 숫자를 모두 붙이면 하나의 수를 만들 수 있는데 이 수를 주어진 부등호 관계를 만족시키는 정수라고 한다. 그런데 주어진 부등호 관계를 만족하는 정수는 하나 이상 존재한다. 예를 들어 3456128790 뿐만 아니라 5689023174도 아래와 같이 부등호 관계 A를 만족시킨다. 

5 < 6 < 8 < 9 > 0 < 2 < 3 > 1 < 7 > 4

여러분은 제시된 k개의 부등호 순서를 만족하는 (k+1)자리의 정수 중에서 최댓값과 최솟값을 찾아야 한다. 앞서 설명한 대로 각 부등호의 앞뒤에 들어가는 숫자는 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }중에서 선택해야 하며 선택된 숫자는 모두 달라야 한다. 

입력

첫 줄에 부등호 문자의 개수를 나타내는 정수 k가 주어진다. 그 다음 줄에는 k개의 부등호 기호가 하나의 공백을 두고 한 줄에 모두 제시된다. k의 범위는 2 ≤ k ≤ 9 이다. 

출력

여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력에 답은 항상 존재하며 출력 정수는 하나의 문자열이 되도록 해야 한다. 

예제 입력 1

2
< >

예제 출력 1

897
021

예제 입력 2

9
> < < < > > > < <

예제 출력 2

9567843012
1023765489

---

🚀문제 접근

완전탐색으로 접근했다. 근거는 k의 범위가 2부터 9까지이기 때문이다. 그런데 최악의 경우에는 재귀연산이 3628800번 수행될 수 있다는 것을 염두해야한다. 

 

먼저 순열을 통해 숫자를 뽑고 숫자 사이사이에 부등호를 넣어서 부등호가 올바른 자리에 위치하는지를 판단하기로 했다.

하지만 아래 코드는 시간초과가 나왔다. 역시 최악의 경우에 굉장히 느린 속도로 정답이 나오는 것을 확인할 수 있었다.

let [k, arr] = require('fs').readFileSync(0).toString().trim().split('\n');

k = Number(k);

arr = arr.split(' ');

function solution() {

  const nums = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];

  const visited = Array.from({ length: nums.length }).fill(0);

  const tmp = [];

  const ret = [];

  const permutation = (depth) => {

    if (depth === k + 1) {

      let flag = 1;

      let a = [];

      for (let i = 0; i < tmp.length - 1; i++) {

        a.push(tmp[i]);

        if (arr[i]) a.push(arr[i]);

        a.push(tmp[i + 1]);

      }

      while (a.length) {

        let b = a.splice(0, 3);

        if (b[1] === '<') {

          if (b[0] > b[2]) {

            flag = 0;

            break;

          }

        } else if (b[1] === '>') {

          if (b[0] < b[2]) {

            flag = 0;

            break;

          }

        }

      }

      if (flag) ret.push(tmp.join(''));

      return;

    } else {

      for (let i = 0; i < nums.length; i++) {

        if (visited[i]) continue;

        visited[i] = 1;

        tmp.push(nums[i]);

        permutation(depth + 1);

        visited[i] = 0;

        tmp.pop();

      }

    }

  };

  permutation(0);

  console.log(ret[ret.length - 1]);

  console.log(ret[0]);

}

solution();

 

중복되는 계산이 없는지 백트래킹을 수행해야한다.

조건에 맞는 경우에만 숫자를 붙여주기로 수정해보자. 이게 무슨 말이냐면,

예를 들어 2 < ⬜ 라는 식에서 네모 안에 들어와야하는 값은 2보다 작은 값이어야한다.

즉, 3, 4, 5 등등 2보다 큰 경우는 제외하고 2보다 작은 값만 문자열에 붙여주자는 것이다.

 

let [k, signs] = require('fs').readFileSync(0).toString().trim().split('\n');

k = Number(k);

signs = signs.split(' ');

const ret = [];

const visited = Array.from({ length: 10 }).fill(0);

const dfs = (l, sum) => {

  if (l === k) {

    ret.push(sum);

  } else {

    const last = sum[sum.length - 1];

    if (signs[l] === '>') {

      for (let i = 0; i < 10; i++) {

        if (!visited[i] && last > i) {

          visited[i] = 1;

          dfs(l + 1, sum + `${i}`);

          visited[i] = 0;

        }

      }

    } else {

      for (let i = 0; i < 10; i++) {

        if (!visited[i] && last < i) {

          visited[i] = 1;

          dfs(l + 1, sum + `${i}`);

          visited[i] = 0;

        }

      }

    }

  }

};

for (let i = 0; i < 10; i++) {

  visited[i] = 1;

  dfs(0, `${i}`);

  visited[i] = 0;

}

console.log(`${ret.pop()}\n${ret.shift()}`);

 

백트래킹을 고려한 코드이다.

이전 코드처럼 모든 경우의 수를 찾아 일일히 부등호 조건이 맞는지 확인하는 것이 아니라 뒤에 붙히는 수가 부등호 조건에 맞는 경우에만 붙히기 때문에 시간을 단축할 수 있다.

그리고 0부터 9까지 차례대로 순회하기 때문에 ret에 들어가는 요소들은 정렬되어 들어간다.