LeetCode - The World's Leading Online Programming Learning Platform
input: 로마숫자 s
output: 로마 숫자를 정수로 변화하여 리턴
로마 숫자는 아래의 경우만 존재
더 작은 로마 숫자가 큰 숫자 앞에 오는 경우 두수의 차를 뜻함
ex) IX → 10 - 1 = 9, CM → 1000 - 100 = 900
1 <= s.length <= 15s contains only the characters ('I', 'V', 'X', 'L', 'C', 'D', 'M').s is a valid roman numeral in the range [1, 3999].
각 로마 문자마다 대응되는 숫자가 있기 때문에, Hash를 이용하려 코드를 작성했다.
하지만 높은 점수를 받지 못했고, 혹시 Hash보다 When(조건문)을 통한 처리가 빠를까 싶어 When으로 코드를 작성하였고 높은 점수를 받았다. ⇒ hash vs array 속도 비교
hashMap을 사용하여 로마 → 정수 변환 ⭕
로마 문자 → 정수, 변환 Map을 생성
앞에서부터 순서대로 변화하다, 내림차순이 아닌 경우만 뺄셈 처리
→ 일단 모두 더하다 내림차순이 아닌 경우 이전의 값을 두배하여 빼주면 됨
(이미 앞에서부터 순서대로 변환하여 더했으므로 두배하여 빼줌)
class Solution {
fun romanToInt(s: String): Int {
val convert = mutableMapOf<Char, Int>('I' to 1, 'V' to 5, 'X' to 10, 'L' to 50, 'C' to 100, 'D' to 500, 'M' to 1000)
var prev = 9999 // 뺄셈 대비하여 이전값 저장
var answer = 0
for (c in s) {
val int = convert[c]!!
// 내림차순이 아닌 경우, 이전의 값을 두배하여 빼줌
answer = if (prev >= int) answer + int else answer + int - prev * 2
prev = int
}
return answer
}
}
시간 복잡도: 문자열 순회 = n
When 구문 사용 (hashMap X) ⭕
⇒ 로마 문자가 7가지(매우 적음) 밖에 없기 때문에, When구문으로 처리
class Solution {
fun romanToInt(s: String): Int {
var prev = 9999 // 뺄셈 대비하여 이전값 저장
var answer = 0
for (c in s) {
val int = when (c) {
'I' -> 1
'V' -> 5
'X' -> 10
'L' -> 50
'C' -> 100
'D' -> 500
'M' -> 1000
else -> 0
}
// 내림차순이 아닌 경우, 이전의 값을 두배하여 빼줌
answer = if (prev >= int) answer + int else answer + int - prev * 2
prev = int
}
return answer
}
}
시간 복잡도: 문자열 순회 = n
