[Leetcode] #13 Roman to Integer 로마 수 변환하기

Posted by on

 문제 요약

자세한 내용은 leetcode에서 확인

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


심볼마다 정해진 값을 가지고 있다.

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

Roman numeral 표기법은 큰 숫자부터 작은 숫자를 나열한다. 


6가지 예외가 있는데 다음과 같다.

- I가 V나 X앞에 붙으면 I값을 더하는 대신 뺀다.

- X가 L이나 C앞에 붙으면 X값을 더하는 대신 뺀다.

- C가 D나 M앞에 붙으면 C값을 더하는 대신 뺀다.


예로 IV는 6이 아닌 5 - 1 = 4가 되는 식이다. 

그 외의 경우는 전부 더하면 된다. XXVII = XX + V + II = 20 + 5 + 2 = 27


풀이

이 문제의 핵심은 큰 숫자부터 작은 숫자 순으로 나열된다는 점이다. 

이 규칙으로 인해 6가지 스페셜 컨디션들의 추가적인 조건들을 알아낼 수 있다. 

- C(100)는 L(50), X(10), V(5) 보다 크기 때문에 이것들보다 앞에 붙을 수 없다.

- X(10)은 V(5)보다 크기 때문에 이것보다 앞에 붙을 수 없다.


핵심 로직은 input 스트링을 for loop으로 돌면서 

- 만약 i 캐릭터의 값이 바로 전 인덱스(i-1)의 값보다 작다면 sum에 더한다.

- 만약 i 캐릭터의 값이 바로 전 인덱스(i-1)의 값보다 크다면 스페셜 컨디션에 부합하기 때문에 i 캐릭터 값에 i-1 캐릭터 값을 한번 빼고, i-1 때 더한 값을 한번 더 빼준다.


// map을 만들어 캐릭터와 수를 매핑해준다.
private static Map<Character, Integer> m = new HashMap<>();
static {
m.put('I', 1);
m.put('V', 5);
m.put('X', 10);
m.put('L', 50);
m.put('C', 100);
m.put('D', 500);
m.put('M', 1000);
}
// roman numeral은 largest to smallest로 표기된다. 꼭 기억하자.
public int romanToInt(String s) {
char[] c = s.toCharArray();
int sum = 0;
for (int i=0; i<c.length; i++) {
// if previous number is greater than current
// it means we need to subtract the previous number

// 만약 현재 캐릭터 값이 바로 전 캐릭터 값보다 더 크면 스페셜 컨디션으로써 바로 전 캐릭터 값을 두 번 빼준다.
if (i > 0 && m.get(c[i]) > m.get(c[i-1])) {
sum += m.get(c[i]) - 2*m.get(c[i-1]);
} else {
// 그 외에 경우엔 sum에 바로 더해준다.
sum += m.get(c[i]);
}
}
return sum;
}


Complexity

time: O(n) - input string 길이 만큼 for loop을 실행한다.

space: O(1) - 몇개 안되는 변수를 생성하였다.