[LeetCode/Kotlin]Medium - 12. Integer to Roman

Integer to Roman - LeetCode

---

문제

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

SymbolValue
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, 2 is written as II in Roman numeral, just two one's added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

• I can be placed before V (5) and X (10) to make 4 and 9.
• X can be placed before L (50) and C (100) to make 40 and 90.
• C can be placed before D (500) and M (1000) to make 400 and 900.

Given an integer, convert it to a roman numeral.

 

Example 1:

Input: num = 3
Output: "III"
Explanation: 3 is represented as 3 ones.

 

Example 2:

Input: num = 58
Output: "LVIII"
Explanation: L = 50, V = 5, III = 3.

 

Example 3:

Input: num = 1994
Output: "MCMXCIV"
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

 

Constraints:

• 1 <= num <= 3999

---

풀이

(1) 나의 풀이법

 

풀이 접근 과정

만들 수 있는 모든 경우의 수를 Map 형식으로 만들어 선언하여 반복문을 통해 값을 도출해내는 방식으로 접근하였다.

class Solution {
    fun intToRoman(num: Int): String {
        var answer = ""
        var newNum = num
        val map = arrayOf(
            Pair("", 0),
            Pair("I", 1),
            Pair("IV", 4),
            Pair("V", 5),
            Pair("IX", 9),
            Pair("X", 10),
            Pair("XL", 40),
            Pair("L", 50),
            Pair("XC", 90),
            Pair("C", 100),
            Pair("CD", 400),
            Pair("D", 500),
            Pair("CM", 900),
            Pair("M", 1000),
            Pair("",2000)
        )

        while (newNum != 0) {
            for (i in 1..< map.size) {
                if (newNum >= 2000) {
                    answer += "M"
                    newNum -= 1000
                    break
                }
                if (newNum in map[i-1].second ..< map[i].second) {
                    answer += map[i-1].first
                    newNum -= map[i-1].second
                    break
                }
            }
        }
        return answer
    }
}

만들어지는 모든 경우의 로마 숫자를 map에 저장한다.

newNum이 0이 아니면 while문을 통해 반복문을 돌린다.

newNum 값이 map의 특정 범위에 존재하면, 해당하는 로마 숫자를 answer에 더해주고, newNum에서 값을 빼준다.

그렇게 newNum이 돌 때까지 반복한다.

2000의 경우, 범위에 걸리지 않으므로 따로 예외 처리를 한다.

 

문제를 정리하다보니 큰 수부터 돌고, 큰 수보다 작아지면 해당 값을 삭제하면 더 간편하게 풀 수 있었을 텐데… 아쉬움이 남았다.

 

최종 소스코드

class Solution {
    fun intToRoman(num: Int): String {
        var answer = ""
        var newNum = num
        val map = mutableListOf(
            Pair("M", 1000),
            Pair("CM", 900),
            Pair("D", 500),
            Pair("CD", 400),
            Pair("C", 100),
            Pair("XC", 90),
            Pair("L", 50),
            Pair("XL", 40),
            Pair("X", 10),
            Pair("IX", 9),
            Pair("V", 5),
            Pair("IV", 4),
            Pair("I", 1)
        )

        while (newNum != 0) {
            if (map.isEmpty()) break
            if (newNum < map[0].second) map.removeAt(0)
            else {
                answer += map[0].first
                newNum -= map[0].second
            }
        }

        return answer
    }
}

 

1. 기존과 그대로 map을 만들지만 큰 숫자부터 만들었다.
2. 만약 map이 비어있지 않고, newNum이 0이 아닌 상태인 경우에만 반복문을 돈다.
3. newNum 값이 map의 첫 인덱스 숫자보다 작다면 map의 첫 값은 제거한다.
4. newNum 값이 map의 첫 인덱스 숫자보다 크거나 같다면 해당 로마 문자를 answer에 추가하고, newNum에 해당 숫자를 빼준다.
5. answer를 리턴한다.

 

다른 풀이법

fun intToRoman(num: Int): String {
    val values = intArrayOf(1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1)
    val romanSymbols = arrayOf("M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I")
    
    var result = StringBuilder()
    var n = num
    
    for (i in values.indices) {
        while (n >= values[i]) {
            result.append(romanSymbols[i])
            n -= values[i]
        }
    }
    
    return result.toString()
}

1. values 배열과 romanSymbols 배열은 로마 숫자 변환에 필요한 값을 저장한다.
   • values 배열에는 정수 값 저장
   • romanSymbols 배열에는 해당 값에 대응하는 로마 숫자 심볼을 저장
2. result는 결과를 저장할 StringBuilder
3. n은 주어진 정수 num을 로마 숫자로 변환하기 위해 사용됨
   • num으로 초기화
4. values 배열을 순회
   • while 루프를 사용하여 n이 현재 값 values[i] 보다 크거나 같을 때까지 반복
   • result에 현재 로마 숫자 심볼 romanSymbols[i]**을 추가하고, n에서 values[i]를 빼서 해당 값이 줄어들게 함.
   • 이 작업을 반복하면서 n을 작은 숫자로 계속 나누고 해당 로마 숫자를 결과 문자열에 추가
5. result 리턴

---

Comment

첫번째 문제 풀이 결과

 

이번 나의 풀이는 썩 만족스럽지 못했다…

큰 수부터 돌고, 큰 수보다 작아지면 해당 값을 삭제하면 더 간편하게 풀 수 있었을 텐데…

아쉬움이 남아서 다시 풀었다.

두번째 문제 풀이 결과

 

놀랍게도 두 풀이의 성능 차이는 그닥 크지 않았다…ㅎㅎ

오히려 메모리가 더 안좋아졌네 ^.^

왜? MutableArray와 Array의 메모리 차이가 있나?