[Leetcode] 12. Integer to Roman - JS
1. 문제 분석
문제분석
--------------------
높은 자리값에서 낮은 값으로 변환하면서 로마 기호로 변환한다.
- 4,9로 시작하지 않는다면, 입력에서 밸 수 있는 최대값 기호를 선택하여 결과에 기호를 추가한 뒤 그 값을 뺀 뒤 나머지를 로마 기호로 변환한다.
- 4,9로 시작한다면, 4는 5보다 1작고 9는 10보다 1작으니 각각 IV(4), IX(9), XL(40), XC(90), CD(400), CM(900)을 사용한다.
- 10의 배수(I, X, C, M)만 최대 3번 연속해서 추가할 수 있다.
- 연속 4번 추가하고 싶으면 빼기 형식을 사용해라.
제한조건
--------------------
- 1 <= num <= 3999
2. 접근 방법
접근방법
--------------------
hash에 roman 기호를 등록하여 변환해주자.
숫자를 문자열로 변환하여 최대 자릿수부터 반복문을 시작한다.
만약 4,9로 시작한다면 hash에서 구해준다.
각 자릿수는 문자열 길이 - 시작인덱스 만큼 10을 곱해서 구해준다.
각 자릿수에서 최댓값인 roman 기호는 hash 값에서 구한다.
각 자릿수의 값이 0이 될 때까지 최댓값을 빼주면서 기호를 구한다.
3. 코드
var intToRoman = function(num) {
const romanHash = {
'1':'I',
'5':'V',
'10':'X',
'50':'L',
'100':'C',
'500':'D',
'1000':'M',
'4':'IV',
'9':'IX',
'40':'XL',
'90':'XC',
'400':'CD',
'900':'CM'
};
let numStr = String(num);
let res = '';
for (let i = 0; i < numStr.length; i++) {
let pow = Math.pow(10, numStr.length - i - 1);
let targetNum = Number(numStr[i]) * pow;
if (numStr[i] === '4' || numStr[i] === '9') {
res += romanHash[String(targetNum)];
} else {
while (targetNum !== 0) {
let maxNum = 1;
Object.keys(romanHash).forEach(num => {
if (targetNum >= Number(num)) {
maxNum = Number(num);
}
});
res += romanHash[String(maxNum)]
targetNum -= maxNum;
}
}
}
return res;
};
4. 복잡도 분석
- 시간복잡도: O(n)
- 공간복잡도: O(1)
시간, 공간 복잡도는 괜찮고 내 머릿속 흐름대로 풀 수 있어서 어렵지 않았다. 하지만 남들이 이해하거나 내가 나중에 보더라도 코드가 복잡한 것 같다.
5. Greedy(그리디) 풀이
제한조건을 보면 n이 많아봐야 3999까지 밖에 되지 않고 로만 기호도 4,9 를 나타내는 기호까지 하더라도 13개 뿐이므로 각 상황에서 최적의 상황을 골라내는 Greedy(그리디) 풀이를 사용해 볼 수 있다.
var intToRoman = function(num) {
const romanNum = {
M: 1000,
CM: 900,
D: 500,
CD: 400,
C: 100,
XC: 90,
L: 50,
XL: 40,
X: 10,
IX: 9,
V: 5,
IV: 4,
I: 1,
}
let res = '';
for (let i of Object.keys(romanNum)) {
if (num === 0) break;
let q = Math.floor(num / romanNum[i]);
if (q === 0) continue;
num -= q * romanNum[i];
res += i.repeat(q);
}
return res;
};
1. romanNum 객체를 높은 숫자부터 내림차순으로 문자를 객체에 등록한다.
2. romanNum 객체를 순회한다.
- romanNum의 최댓값으로 num을 나눈 몫을 구한다.
- num에서 최댓값을 나눈 몫과 곱한 만큼 뺀다.
- res에 로만 기호를 몫만큼 반복하여 완성된 문자를 추가한다.
만약 num이 0이 되면 더 이상 문자를 변환할 수 없으므로 반복문을 종료한다.
또한, q가 0이면 굳이 불필요하게 num에서 값을 빼주거나 res에 문자열을 추가해주는 작업을 해줄 필요가 없으므로 다음 순회를 이어가도록 코드를 추가해주었다.
예를 들어, num = 3749 라면
첫번째 순회
i = M
q = Math.floor(3749 / 1000) = 3
num -= 3 * 1000
res += M.repeat(3)
num = 749
res = MMM
두번째 순회
i = CM
q = Math.floor(749 / 900) = 0
num = 749
res = MMM
세번째 순회
i = D
q = Math.floor(749 / 500) = 1
num -= 1 * 500
res += D.repeat(1)
num = 249
res = MMMD
중략...
마지막 순회
i = IX
q = Math.floor(9 / 9) = 1
num -= 1 * 9
res += IX.repeat(1)
num = 0
res = MMMDCCXLIX