문제
제한 사항
입출력 예
풀이
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];
if (expression[L] == ">") {
for (let i = 0; i < 10; i++) {
if (!str.includes(`${i}`) && last > i) {
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과 비교하는 방법도 가능 할 것이다.