백준 2529번: 부등호 - javascript

백준 15661번: 링크와 스타트

문제 설명

접기/펼치기

두 종류의 부등호 기호 ‘<’와 ‘>’가 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인 경우도 정수에 포함되어야 한다. 모든 입력에 답은 항상 존재하며 출력 정수는 하나의 문자열이 되도록 해야 한다.

예시

접기/펼치기

입력
2
< > 

출력
897
021

접근

뭔가 익숙한 느낌인데, 그냥 조건이 붙은 백준 15649번 N과M문제다.

• 뽑을 수 있는 숫자는 0부터 9까지.
• 뽑은 숫자는 중복되면 안된다.
• 0에서 9까지의 숫자 중 부등호 개수 K+1개만큼의 숫자를 뽑아야한다.

이부분만 보면 N과M이랑 거의 비슷하다.
그리고 추가로 붙는 조건,

• 뽑은 숫자들은 제시된 부등호 관계를 만족해야한다.
• 뽑은 숫자들 중 최소값과 최대값을 각각 출력해야한다.

백준 15649번 N과M에 써놓은 풀이를 먼저 보고 오시는 것을 추천드린다.
다 보고 오셨으면 그 뒤부터는 매우 간단하다.

먼저 우리는 부등호와 앞의 숫자에 따라서 다음 숫자를 결정할 것이기 때문에 맨처음에는 0부터 9까지의 반복문을 돌려서 첫번째 숫자를 정하고 재귀함수를 호출한다.

그 뒤에 재귀함수에서는 주어진 부등호들을 stats 배열에 입력받고 중복체크를 한 뒤에 stats의 깊이에 따른 인덱스 값이 > 부등호 인지 < 부등호 인지 체크하고 그에 따라 현재 i 값이 이전 수열 값보다 큰지 작은지의 조건을 추가로 붙인다.

그 뒤에는 기존과 같게 재귀를 해나간다.
최종적으로 주어진 깊이(부등호 개수 k)에 도달하게되면 지금까지 모은 수열 list를 각각 전역변수 min, max와 각각 min비교, max비교를 해준다.
이때, 나는 삼항 연산자를 썼다.
문제에 첫 자리가 0인 경우도 정수에 포함되어야 한다. 라는 조건이 걸려있었기 때문에 삼항 연산자를 사용해서 비교할때만 list 수열을 정수형으로 바꿔서 비교하고, 실제 min에 들어가는 값은 문자열로서의 list 수열이 들어가게 했다.

정답 코드

const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});
let input = [];
let stats = [];
let list = [];
let min = 9999999999;
let max = 0;
let check = [];
rl.on('line', function (line) {
  input.push(line);
})
  .on('close', async function () {
  // 답안 작성
  const m = input.shift()*1;
  stats = input[0].split(' ');
  check = new Array(10).fill(false);  
  for(let i=0;i<10;i++){
    check[i] = true;
    list[0] = i;
    re(0, 10, m, i);
    check[i] = false;
  }    
  console.log(max+'\n'+min);
  process.exit();
});

let re = function(cnt,n,m,back){    
  if(cnt===m){        
    min = (min < list.join('')*1) ? min : list.join('');
    max = (max > list.join('')*1) ? max : list.join('');
    return ;
  }
  for(let i=0;i<n;i++){    
    if(!check[i]){      
      if(stats[cnt]=='<'&& back<i){
        check[i] = true;            
        list[cnt+1] = i;
        re(cnt+1,n,m,i);      
        check[i] = false;
      }else if(stats[cnt]=='>'&& back>i){
        check[i] = true;            
        list[cnt+1] = i;
        re(cnt+1,n,m,i);      
        check[i] = false;
      }      
    }
  }
  return ;
}