LeetCode

12. Integer to Roman

MAXWILL 2024. 11. 30. 13:20
반응형

문제

Seven different symbols represent Roman numerals with the following values:

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

Roman numerals are formed by appending the conversions of decimal place values from highest to lowest. Converting a decimal place value into a Roman numeral has the following rules:

  • If the value does not start with 4 or 9, select the symbol of the maximal value that can be subtracted from the input, append that symbol to the result, subtract its value, and convert the remainder to a Roman numeral.
  • If the value starts with 4 or 9 use the subtractive form representing one symbol subtracted from the following symbol, for example, 4 is 1 (I) less than 5 (V): IV and 9 is 1 (I) less than 10 (X): IX. Only the following subtractive forms are used: 4 (IV), 9 (IX), 40 (XL), 90 (XC), 400 (CD) and 900 (CM).
  • Only powers of 10 (I, X, C, M) can be appended consecutively at most 3 times to represent multiples of 10. You cannot append 5 (V), 50 (L), or 500 (D) multiple times. If you need to append a symbol 4 times use the subtractive form.

Given an integer, convert it to a Roman numeral.

 

Example 1:

Input: num = 3749

Output: "MMMDCCXLIX"

Explanation:

3000 = MMM as 1000 (M) + 1000 (M) + 1000 (M)
 700 = DCC as 500 (D) + 100 (C) + 100 (C)
  40 = XL as 10 (X) less of 50 (L)
   9 = IX as 1 (I) less of 10 (X)
Note: 49 is not 1 (I) less of 50 (L) because the conversion is based on decimal places

Example 2:

Input: num = 58

Output: "LVIII"

Explanation:

50 = L
 8 = VIII

Example 3:

Input: num = 1994

Output: "MCMXCIV"

Explanation:

1000 = M
 900 = CM
  90 = XC
   4 = IV

 

Constraints:

  • 1 <= num <= 3999

 

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

 

 

풀이

로마문자와 값을 큰 숫자부터 작은 숫자 순서로 배열에 넣어서, 큰 숫자부터 로마문자 변환하여 StringBuilder에 저장하도록 했다.

4나 9일 때만 빼는 형태로 작성해야 하니 검사할 값으로 나눈 몫이 4인지 체크했고, 큰 수부터 비교하기 때문에 9의 경우에는 이전에 5 형태의 숫자에서 몫 1과 나머지 4로 5에 대한 로마문자 이후 4가 있을거기 때문에 몫이 4인 경우에 이전 로마 문자와 StringBuilder에 저장된 마지막 로마문자가 같은 경우 9인 것으로 판단하도록 했다.

4xx나 4x와 같이 input이 4로 시작되는 숫자의 경우 9인지 체크할 때 아직 StringBuilder에 값이 없어서 에러가 날 수 있으니 , 5 형태의 숫자로 나눈 이후의 4인지의 체크하도록 StringBuilder에 문자가 있을 경우에 체크하도록 조건을 추가했다.

 

1000, 900, 500, 400, 100 처럼 사이에 4나 9로 시작하는 숫자들에 대한 내용도 추가하여, input 값에서 계속 빼면서 넣도록 진행한다면 속도를 더 줄일 수 있을 것 같지만, 문제의 제한사항인 input 4000 미만이 아닌  로마 숫자의 가로줄 대신 다른 형태로 큰 수 표현을 나타낼 수 있는 경우 자리수가 커질 수록 메모리 사용량이 증가하지 않을까 싶어 비교하면서 문자로 만들도록 진행해봤다.

 

코드

class Solution {
    public String intToRoman(int num) {
        char[] symbol = {'M', 'D', 'C', 'L', 'X', 'V', 'I'};
    	int[] value = {1000, 500, 100, 50, 10, 5, 1}; 
    	StringBuilder res = new StringBuilder();
    	
    	
    	for(int i = 0; i < value.length; i++) {
    		int check = num / value[i];
    		if(check == 4) {
    			if(res.length() > 0 && res.charAt(res.length()-1) == symbol[i-1]) {
    				res.deleteCharAt(res.length()-1);
    				res.append(symbol[i]).append(symbol[i-2]);
    			} else {    				
    				res.append(symbol[i]).append(symbol[i-1]);
    			}
    		} else {
    			for(int append = 0; append < check; append++) {
    				res.append(symbol[i]);
    			}
    		}
    		num %= value[i];
    	}
    	
        return res.toString();
    }
}

 

 

결과

Runtime : 3 ms

Memory Usage : 44.15 MB

 

 

 

 

반응형