[LeetCode][Java] Integer To Roman

최지수·2021년 10월 4일

Java Problem Solving algorithm leetcode

Algorithm

목록 보기

17/77

존재하는 알고리즘을 활용하는 것보단 아이디어가 주가 되는 문제였습니다. 덤으로 사용 언어에 대한 활용법도 정확히 알고 있어야 최적화도 가능하다는 걸 배웠습니다..ㅎㅎ

문제

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

Symbol	Value
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.

제한사항

1 $\leq$ num $\leq$ 3999

접근1

정수를 Roman 표기식으로 변환하는 문제입니다.

저는 천, 백, 십, 일 단위로 숫자를 쪼갠 다음에 단위별로 문자를 주어,

1~3에 대한 예외 처리
4에 대한 예외 처리
5~8에 대한 예외 처리
9에 대한 예외 처리

각 숫자마다 예외 처리를 해서 푸는 방식을 생각했습니다.

답안

class Solution {

    public String toStr(int number, int offset,
                        String unit,
                        String unitFive,
                        String unitNine)
    {
        String ret = new String();
        number = (number - (number % offset)) / offset;
        if(number < 5){
            if(number == 4){
                ret = unit + unitFive;
            } else{
                for(int i = 0; i < number; ++i){
                    ret += unit;
                }
            }
        } else{
            if(number == 9){
                ret += unit + unitNine;
            } else{
                ret = unitFive;
                for(int i = 5; i < number; ++i){
                    ret += unit;
                }
            }
        }
        return ret;
    }

    public String intToRoman(int num) {
        String answer = new String();

        // Thousand
        int thousands = num - (num % 1000);
        for(int i = 0; i < thousands / 1000 ; ++i)
            answer += "M";

        // Hundred
        num %= 1000;
        answer += toStr(num, 100, "C", "D", "M");

        // Ten
        num %= 100;
        answer += toStr(num, 10, "X", "L", "C");

        // Digit
        num %= 10;
        answer += toStr(num, 1, "I", "V", "X");

        return answer;
    }

}

접근2

그러다 문득, 다른 사람들은 어떻게 접근했나 확인했더니, 훨씬 간결하고 효율적으로 짰더라구요...

예외들을 배열Array로 모아, 해당 수치보다 낮을 때까지 빼가면서 답을 구했습니다.1~9로 수치화하고 예외 처리를 한 제 로직과는 달리, 빼기 연산만 수행하니 훨씬 간결하고 효율적인 코드였습니다. 추가로, Java를 접한지 얼마 되지 않은 저에겐 ~~핑계라고 생각합니다... 아직 좀더 노력해야한다고 생각해요~~ 다소 생소한 StringBuilder를 통해 훨씬 편하게 코드를 짰습니다.

아래는 3 ms의 처리 결과가 나온 코드입니다.(제 건 20 ms)

답안2

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