리트코드 - 12. Integer to Roman

리트코드 - 12. Integer to Roman

출처 - https://leetcode.com/problems/integer-to-roman/description/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

로마 숫자는 일곱 가지 다른 기호로 나타낼 수 있습니다: I, V, X, L, C, D 및 M.

기호 값
I 1
V 5
X 10
L 50
C 100
D 500
M 1000

예를 들어, 2는 로마 숫자로 II로 나타냅니다. 즉, 두 개의 1을 합친 것입니다. 12는 XII로 나타내며, 단순히 X + II입니다. 숫자 27은 XXVII로 나타내며, XX + V + II입니다.

로마 숫자는 일반적으로 왼쪽에서 오른쪽으로 크기가 큰 순서로 작성됩니다. 그러나 4에 대한 기호는 IIII가 아닙니다. 대신, 숫자 4는 IV로 쓰여집니다. 왜냐하면 1이 5 앞에 있기 때문에 1을 빼서 4가 됩니다. 동일한 원리가 숫자 9에도 적용되어 IX로 쓰여집니다. 여기서 뺄셈이 사용되는 여섯 가지 경우가 있습니다:

I는 5 (V) 및 10 (X) 앞에 놓여 4 및 9를 만들 수 있습니다.
X는 50 (L) 및 100 (C) 앞에 놓여 40 및 90을 만들 수 있습니다.
C는 500 (D) 및 1000 (M) 앞에 놓여 400 및 900을 만들 수 있습니다.

 

제한조건 : 1 <= num <= 3999

 

의사코드

symbols = 로마 심볼 저장 values = 로마 심볼에 해당하는 숫자 저장 StringBuilder answer = new StringBuilder quot = 0    반복문 시작     quot = num / values[i]     num %= values[i]     quot 갯수만큼 answer에 해당 symbol을 더함 반복문 종료 answer.toString 리턴

 

풀이코드

class Solution {
    public String intToRoman(int num) {
        String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        StringBuilder answer = new StringBuilder();
        int quot = 0;
        for (int i = 0; i < symbols.length; i++) {
            quot = num / values[i];
            num %= values[i];
            for (int j = 0; j < quot; j++) {
                answer.append(symbols[i]);
            }
        }
        
        return answer.toString();
    }
}

 

코드설명

숫자가 주어지면 로마자로 변환하는 문제이다.

문제를 처음 마주치면 4와 9를 처리하는 것이 무척 까다롭다고 생각이 드는데, 배열을 두 개 만들면 쉽게 해결된다.

 

symbols 배열에는 로마자를 넣고, values 배열에는 해당하는 숫자를 넣어놓고 반복문을 돌리면 간단히 해결된다.

String보다 효율이 좋은 StringBuilder를 활용하여 풀었다.

 

요구사항에 따라 다르겠지만, 이 문제는 if문으로 분기를 나눈게 오히려 복잡해지는 문제이다.

 

만약 문제에서 주어진 조건이 int가 아니라 String으로 주어진 경우에도 String 클래스의 charAt 메소드를 활용하여 풀면 된다.

 

시간복잡도 - O(1) (주어진 num의 크기와 상관없이 symbols만큼의 시간만 필요)

공간복잡도 - O(1)

 

문제를 풀며 생각한 흐름과 배운 점

예전에 어디 코딩테스트에서 해당 문제가 나왔었는데 못 풀었었다.

if문의 지옥에 빠졌다가 결국 풀어내지 못했는데, 그 때 공부해두었던 문제가 이번에 나왔다.

 

아마 다른 응용 문제들도 있는 걸로 아는데 빨리 풀어보고 싶다는 생각이다.

 

정리

숫자가 주어지면 로마 넘버로 바꾸는 방법