https://leetcode.com/problems/integer-to-roman
Symbol 별로 숫자가 할당되어 있다.
10진수의 수를 이제 로마수로 변경해야 한다. 변경은 다음과 같은 과정을 통한다.
- 수가 4 혹은 9로 시작하지 않는다면 input으로부터 뺄 수 있는 최대 symbol을 선택한다. 그리고 해당 symbol을 결과에 추가한다. 그리고 해당 숫자를 뺀 나머지를 로마수로 재할당한다.
- 만약 수가 4 혹은 9로 시작하다면, 해당 값을 뺄샘 형태로 변환하여 로마수로 표현한다. 예를 들어 4는 5(V)에서 1(I)을 뺀 값이 되므로 IV가 된다.
- 10의 거듭제곱은 최대 3번까지 연속해서 붙일 수 있다. 하지만 5(V), 50(L), 500(D)은 여러 번 반복해서 사용할 수 없다. 만약 어떤 기호가 4번 반복해서 사용해야 할 경우에는 뺄셈 형태로 변환한다.
우선 하나씩 생각해보자.
주어진 숫자 num의 첫자리 숫자를 어떻게 판단 할 것인가?
4냐 400이냐에 따라 조합이 달라지기 때문에 첫 자리 숫자가 어떤 수인지를 넘어 자릿수까지 판단을 해야 한다.
문자열로 판단하는 게 낫겠다는 생각이 든다. int num = 3749라고 가정해 보자.
문자열로 바꾸면 “3749”, 길이가 4인 문자열이 된다.
첫자리는 3 * 10 ^4 그다음은 7 * 10^3, 410^2, 910^1 이렇게 된다. 매 순간 판단하는 숫자가 문자열의 길이와 chartAt(n)으로 편리하게 구할 수 있다.
class Solution {
private static final Map<Integer, String> symbolMap = new LinkedHashMap<>();
static {
symbolMap.put(1000, "M");
symbolMap.put(500, "D");
symbolMap.put(100, "C");
symbolMap.put(50, "L");
symbolMap.put(10, "X");
symbolMap.put(5, "V");
symbolMap.put(1, "I");
}
public String intToRoman(int num) {
StringBuilder sb = new StringBuilder();
String number = Integer.toString(num);
int length = number.length();
for (int i = 0; i < length; i++) {
int coefficient = number.charAt(i) - '0';
int exponent = length - i - 1;
int now = coefficient * (int)Math.pow(10, exponent);
if (coefficient == 4 || coefficient == 9) {
for (int key : symbolMap.keySet()) {
if (key > now && symbolMap.containsKey(key - now)) {
sb.append(symbolMap.get(key - now));
sb.append(symbolMap.get(key));
}
}
} else {
for (int key : symbolMap.keySet()) {
while (now >= key) {
now -= key;
sb.append(symbolMap.get(key));
}
}
}
}
return sb.toString();
}
}
일단 통과는 됐다.
간단하게 설명하자면 우선 LinkedHashMap을 사용해 데이터를 삽입된 순서대로 저장되도록 처리했다.
그 후 주어진 num을 문자로 변경하고 이 문자열을 조작해 문제를 풀었다.
그런데 매 숫자마다 일일이 확인하고 변환하는 과정 때문에 효율적이지 않다.
그러면 애초에 가능한 로마 symbol을 다 저장해 놓으면 되는 거 아닐까? 생각보다 개수가 몇 개 없으니 가능한 방식이다.
class Solution {
private static final Map<Integer, String> SYMBOL_MAP = new LinkedHashMap<>();
static {
SYMBOL_MAP.put(1000, "M");
SYMBOL_MAP.put(900, "CM");
SYMBOL_MAP.put(500, "D");
SYMBOL_MAP.put(400, "CD");
SYMBOL_MAP.put(100, "C");
SYMBOL_MAP.put(90, "XC");
SYMBOL_MAP.put(50, "L");
SYMBOL_MAP.put(40, "XL");
SYMBOL_MAP.put(10, "X");
SYMBOL_MAP.put(9, "IX");
SYMBOL_MAP.put(5, "V");
SYMBOL_MAP.put(4, "IV");
SYMBOL_MAP.put(1, "I");
}
public String intToRoman(int num) {
StringBuilder sb = new StringBuilder();
for (int key : SYMBOL_MAP.keySet()) {
while (num >= key) {
num -= key;
sb.append(SYMBOL_MAP.get(key));
}
}
return sb.toString();
}
}
그런데 더 개선할 점이 있는 것 같다.
데이터셋 저장을 LinkedHashMap을 사용함으로써 삽입 순서를 유지한 것은 좋았지만 각 반복에서 Map의 엔트리에 접근하는 데 추가적인 동작이 들어간다.
LinkedHashMap은 내부적으로 LinkedList를 사용하니까 메모리 접근이 배열에 비해서 덜 효율적일 수 있다.
따라서 해당 저장을 두 개의 배열로 나누어 저장해서 접근하면 조금 더 효율적인 결과를 얻을 수 있을 것이다.
class Solution {
private static final int[] VALUES = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
private static final String[] SYMBOLS = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
public String intToRoman(int num) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < VALUES.length; i++) {
while (num >= VALUES[i]) {
num -= VALUES[i];
sb.append(SYMBOLS[i]);
}
}
return sb.toString();
}
}
이 문제는 결국 공간과 시간의 트레이드오프를 보여줬던 문제였던 것 같다.
