Question
아래와 같은 과정을 거쳐 부등호 수(inequalityNumber)를 만들 수 있습니다.
•
최대 9개의 부등호(<, >)가 주어집니다.
•
부등호의 좌우에는 0부터 9사이의 숫자가 한 번씩만 들어가야 합니다.
•
부등호를 만족하는 숫자의 조합을 차례대로 이어 붙여 만든 정수를 부등호 수라고 한다.
부등호 기호들을 입력받아 부등호를 만족하는 최대 부등호 수와 최소 부등호 수의 차이를 리턴해야 합니다.
주의사항
•
첫 자리가 0인 경우도 부등호 수에 포함되어야 합니다.
•
모든 입력에 답은 항상 존재합니다.
Test Case 1
let output = inequalityNumber('<');
console.log(output); // --> 88 (89 - 01)
Shell
복사
Test Case 2
output = inequalityNumber('> < >');
console.log(output); // --> 8,754 (9,786 - 1,032)
Shell
복사
Solve
재귀 DFS?
const inequalityNumber = function (signs) {
signs = signs.split(' ');
const numArr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
// 유효한지 확인하는 함수
const isValid = function (numArr, signIdx, check, num) {
// 수를 다 찾았다면 그 값을 리턴
if (signIdx === signs.length) return parseInt(num.join(''));
// 아직 못찾았다면
const currentSign = signs[signIdx];
// 숫자 하나씩 차례대로 넣어보기
for (let i = 0; i < numArr.length; i++) {
const now = numArr[i];
// 이미 넣은 숫자면 패스
if (check[now] === true) continue;
// 첫번째 숫자가 아닐 때, 부등호와 일치하지 않는 숫자도 패스
if (signIdx >= 0) {
const prev = num[num.length - 1];
if (currentSign === '<' && prev >= now) continue;
if (currentSign === '>' && prev <= now) continue;
}
// 만족하는 값이라면 이미 넣은 숫자 체크해주고 재귀로 다음 숫자 넣어보기
check[now] = true;
const next = isValid(numArr, signIdx + 1, check, num.concat(now));
// 이후의 값을 찾을 수 있는지 확인
if (next !== -1) return next;
// 이후의 값 찾을 수 없다면 체크 비활성화
check[now] = false;
}
// 넣을 수 있는 값이 없다면
return -1;
};
const minNum = isValid(numArr, -1, Array(10).fill(false), []);
const maxNum = isValid(numArr.reverse(), -1, Array(10).fill(false), []);
return maxNum - minNum;
}
JavaScript
복사
첫 숫자는 무조건 넣어야하므로 signIdx의 시작을 -1로
실행시간 : ms