[LeetCode] 12. Integer to Roman / JAVA

>> 문제설명

leetcode.com/problems/integer-to-roman/

Integer to Roman - LeetCode

> Solution 1 (No Array)

class Solution {
    public String intToRoman(int num) {
        String answer = "";

        for(int idx = 0; idx < num / 1000; idx++) answer = answer.concat("M");
        num %= 1000;
        for(int idx = 0; idx < num / 900; idx++) answer = answer.concat("CM");
        num %= 900;
        for(int idx = 0; idx < num / 500; idx++) answer = answer.concat("D");
        num %= 500;
        for(int idx = 0; idx < num / 400; idx++) answer = answer.concat("CD");
        num %= 400;
        for(int idx = 0; idx < num / 100; idx++) answer = answer.concat("C");
        num %= 100;
        for(int idx = 0; idx < num / 90; idx++) answer = answer.concat("XC");
        num %= 90;
        for(int idx = 0; idx < num / 50; idx++) answer = answer.concat("L");
        num %= 50;
        for(int idx = 0; idx < num / 40; idx++) answer = answer.concat("XL");
        num %= 40;
        for(int idx = 0; idx < num / 10; idx++) answer = answer.concat("X");
        num %= 10;
        for(int idx = 0; idx < num / 9; idx++) answer = answer.concat("IX");
        num %= 9;
        for(int idx = 0; idx < num / 5; idx++) answer = answer.concat("V");
        num %= 5;
        for(int idx = 0; idx < num / 4; idx++) answer = answer.concat("IV");
        num %= 4;
        for(int idx = 0; idx < num / 1; idx++) answer = answer.concat("I");

        return answer;
    }
}

>Result 1

> Solution 2 (No Loop)

class Solution{
    public String intToRoman(int num){
        String[] MMap = {"","M","MM","MMM"};
        String[] CMap = {"","C","CC","CCC","CD","D","DC","DCC","DCCC","CM"};
        String[] XMap = {"","X","XX","XXX","XL","L","LX","LXX","LXXX","XC"};
        String[] IMap = {"","I","II","III","IV","V","VI","VII","VIII","IX"};
        return MMap[num/1000].concat(CMap[num/100%10]).concat(XMap[num/10%10]).concat(IMap[num%10]);
    }
}

>Result 2

 

확실히 연산이 적을 것 같은 방식으로 풀이해도 Runtime의 차이가 나지 않아서 아쉽다.

Solution 1이 String 배열을 4개나 선언한 Solution 2보다 메모리를 많이 사용한다는 점은 놀랍다.

각 for문마다 작동하는 concat의 작동방식이 더하려는 값을 new String으로 만들어 붙이는 내부구조를 가져서 그럴 것 같다.

 

그렇다면 StringBuilder는 어떨까

> Solution 2-1

class Solution{
    public String intToRoman(int num){
        String[] MMap = {"","M","MM","MMM"};
        String[] CMap = {"","C","CC","CCC","CD","D","DC","DCC","DCCC","CM"};
        String[] XMap = {"","X","XX","XXX","XL","L","LX","LXX","LXXX","XC"};
        String[] IMap = {"","I","II","III","IV","V","VI","VII","VIII","IX"};
        StringBuilder sb = new StringBuilder();
        return sb.append(MMap[num/1000]).append(CMap[num/100%10]).append(XMap[num/10%10]).append(IMap[num%10]).toString();
    }
}

 

> Result 2-1

미미하게 0.3MB정도의 메모리를 절약했다.