단조 증가 숫자(Monotonically Increasing Digits)란?
어떤 정수의 모든 인접한 두 자릿수 x와 y에 대해 x <= y가 항상 성립할 때, 그 정수는 단조 증가하는 자릿수를 가진다고 정의합니다.
예를 들어 1234나 2299처럼 왼쪽에서 오른쪽으로 갈수록 자릿수가 커지거나 같게 유지되는 수는 단조 증가 숫자입니다. 반면 332처럼 중간에 자릿수가 줄어드는 지점이 존재하는 수는 해당하지 않습니다.
문제 설명
숫자 num을 첫 번째이자 유일한 인수로 받는 JavaScript 함수를 작성해야 합니다.
이 함수는 num보다 작거나 같은 수 중에서 단조 증가하는 자릿수를 가진 가장 큰 수를 찾아 반환해야 합니다.
예를 들어 함수의 입력이 다음과 같다면,
입력
const num = 332;
출력
const output = 299;
결과가 299인 이유는 332 이하의 수 중에서 자릿수가 단조 증가하는 가장 큰 수가 299이기 때문입니다. 실제로 300부터 332까지의 어떤 수도 단조 증가 조건을 만족하지 않습니다.
풀이 접근 방식
이 문제는 다음과 같은 전략으로 해결할 수 있습니다.
- 먼저 주어진 수 자체가 이미 단조 증가하는지 확인하고, 그렇다면 그대로 반환합니다.
- 그렇지 않다면 각 자릿수 위치마다 해당 자릿수를 1 감소시키고, 그 뒤의 모든 자릿수를 9로 채운 후보 수를 생성합니다.
- 각 후보 수가 단조 증가 조건을 만족하는지 검사한 뒤, 유효한 후보 중 최댓값을 결과로 반환합니다.
예를 들어 332의 경우, 첫 번째 자릿수인 3을 2로 줄이고 나머지 자릿수를 9로 채운 299가 단조 증가 조건을 만족하므로 정답이 됩니다.
예제 코드
다음은 위 로직을 구현한 전체 코드입니다 −
const num = 332;
const monotoneIncreasingDigits = (num) => {
const checkMonotone = (x) =>{
if (x <= 9) {
return true
}
let currentDigit = x % 10
while (x) {
const next = Math.floor(x / 10)
const nextDigit = next % 10
if (currentDigit >= nextDigit) {
currentDigit = nextDigit
x = next
} else {
return false
}
}
return true
}
if (checkMonotone(num)) {
return num
}
const digits = num.toString().split('').map(x => Number(x))
return digits.reduce((acc, num, index) => {
if (num >= 1) {
const current = parseInt(digits.slice(0, index).join('') + num - 1 + new Array(digits.length - index - 1).fill('9').join(''), 10)
if (checkMonotone(current)) {
return Math.max(
acc,current)
}
}
return acc
}, 0)
}
console.log(monotoneIncreasingDigits(num));출력 결과
299
코드 동작 원리
checkMonotone함수는 숫자를 한 자릿수씩 분해하며, 인접한 자릿수가 감소하는 지점이 있는지 검사합니다. 한 번이라도 감소하면 즉시false를 반환합니다.reduce메서드를 사용해 각 자릿수 위치에서 "그 자릿수를 1 줄이고 뒤의 자릿수를 모두 9로 채운" 후보 수를 만듭니다.- 생성된 후보 수가 단조 증가 조건을 통과하면
Math.max로 기존 최댓값과 비교하여 더 큰 값을 유지하고, 마지막에 그 값을 반환합니다.