[알고리즘] 백준 2529 - 부등호 (JS)

✅ 문제

종류의 부등호 기호 ‘<’와 ‘>’가 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 }중에서 선택해야 하며 선택된 숫자는 모두 달라야 한다.

 

✅ 조건

시간 제한 메모리 제한

1 초

256 MB

✅ 입력

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

 

✅ 출력

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

 

✅ 풀이

k의 범위가 크지 않기 때문에 순열을 이용한 완전 탐색으로 풀이하려고 했지만 메모리 초과 벽에 부딪힘. (제너레이터를 사용하면 메모리 초과를 넘길 수 있다고 한다. → 시도해볼것.)

1시간 동안 고민해도 풀이가 떠오르지 않아 다른 사람의 코드를 참고해서 풀이했다. (DFS를 사용한다.)

// 부등호의 개수
const k = Number(input.shift());
// 부등호 배열 
const A = input[0].split(" ");
const answer = [];

function DFS(str,cnt){
  if(cnt==k){
    answer.push(str);
    return;
  }else{
    const last = str[cnt];
    if(A[cnt]=='>'){
      for(let i = 0; i<10; i++){
        if(!str.includes(`${i}`) && last>i){
           DFS(str+`${i}`,cnt+1)
        }
      }
    }else{
      for(let i = 0; i<10; i++){
        if(!str.includes(`${i}`) && last<i){
           DFS(str+`${i}`,cnt+1)
        }
      }
    }
  }
}

for(let i = 0; i<10; i++){
  DFS(`${i}`,0);
}

console.log(answer.pop()+'\\n'+answer.shift())

부등호 사이에 들어갈 수 있는 숫자는 0~9 까지 이므로 for 문 안에서 DFS를 호출해준다. 백트래킹 알고리즘을 사용해서 cnt와 k가 같을 경우 이전 탐색으로 돌아오도록 한다.

 

아래는 순열을 이용한 풀이이다.

// 부등호의 개수
const k = Number(input.shift());
// 부등호 배열 
const A = input[0].split(" "); 
// 각 부등호의 앞 뒤에 들어갈 수 있는 숫자 (중복 안됨.)
const pos = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];

const getPermutations = function (arr, selectNumber) {
    const results = [];
    if (selectNumber === 1) return arr.map((value) => [value]); // 1개씩 택할 때, 바로 모든 배열의 원소 return
  
    arr.forEach((fixed, index, origin) => {
      const rest = [...origin.slice(0, index), ...origin.slice(index + 1)]; // 해당하는 fixed를 제외한 나머지 배열
      const permutations = getPermutations(rest, selectNumber - 1); // 나머지에 대해 순열을 구한다.
      const attached = permutations.map((permutation) => [fixed, ...permutation]); // 돌아온 순열에 대해 떼 놓은(fixed) 값 붙이기
      results.push(...attached); // 배열 spread syntax 로 모두다 push
    });
  
    return results; // 결과 담긴 results return
  };

  const answer = [];

getPermutations(pos, k + 1).forEach(item => {
    for (let i = 0; i < item.length; i++) {
        let flag = true;
    
        for (let j = 0; j < A.length; j ++) {
            if(A[j] === ">") {
                if(!(item[j] > item[j+1])) {
                    flag = false;
                }
            }else {
                if(!(item[j] < item[j+1])) {
                    flag = false;
                }
            }
        }
    
        if(flag) {
            answer.push(item.join(""));
        };
    }
});

console.log(answer.pop()+'\\n'+answer.shift());

 

• JS 제너레이터에 대해 학습함.