백준 2529 부등호

문제

제한 사항

입출력 예

풀이

let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const sol = (input) => {
  const n = +input.shift();
  const expression = input[0].split(" ");

  const answer = [];

  const dfs = (L, str) => {
    if (L == n) {
      answer.push(str);
      return;
    } else {
      const last = str[str.length - 1]; // str에 저장된 마지막 요소
      if (expression[L] == ">") {
        for (let i = 0; i < 10; i++) {
          if (!str.includes(`${i}`) && last > i) {
            // str에 i가 아직 포함 안되어있고 i가 마지막 요소보다 작으면 (>니까)
            // include 대신 visited배열을 만들어서 사용 할 수도 있을 것이다.
            dfs(L + 1, str + `${i}`);
          }
        }
      } else {
        for (let i = 0; i < 10; i++) {
          if (!str.includes(`${i}`) && last < i) {
            dfs(L + 1, str + `${i}`);
          }
        }
      }
    }
  };
	 
  // 시작 숫자가 바뀜에 따라 다양한 경우의 수가 나오는 것.
  for (let i = 0; i < 10; i++) {
    dfs(0, `${i}`); 
  }
  return `${answer.pop()}\n${answer.shift()}`;
};
console.log(sol(input));

• 백트래킹
• 백트래킹 함수의 매개변수로 L과 str을 준다. L은 depth이자 cnt를 의미하고 str은 현재까지 만들어진 문자열(숫자의 조합)을 나타낸다.
• expression의 종류에 따라 str의 마지막 요소와 다음에 넣을 숫자를 적절하게 비교하여 str에 더해나간다.
• 모든 경우가 answer 배열에 오름차순으로 저장된다.
• 시간 초과가 없다면 순열로 10개중 3개를 뽑는 모든 경우를 구한 후 expression과 비교하는 방법도 가능 할 것이다.