해쉬_LeetCode_RomanToInteger

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

Roman to Integer - LeetCode

 

착안

문제를 보고, string을 한 글자씩 분리하여 case로 나누어 풀이해야겠다고 생각.

1. input string을 분리

2. enum으로 변환

3. 문제 로직에 맞게 풀이

 

코드

초창기 코드

class Solution {
    func romanToInt(_ s: String) -> Int {
        enum roman: Int {
        case one = 1
        case five = 5
        case ten = 10
        case fifty = 50
        case hundred = 100
        case five_hundered = 500
        case thousand = 1000
    }
    
    let stringArray = s.map({$0})
    var converted :[roman] = []
    for spell in stringArray {
        switch spell {
        case "I":
            converted.append(roman.one)
        case "V":
            converted.append(roman.five)
        case "X":
            converted.append(roman.ten)
        case "L":
            converted.append(roman.fifty)
        case "C":
            converted.append(roman.hundred)
        case "D":
            converted.append(roman.five_hundered)
        case "M":
            converted.append(roman.thousand)
        default:
            print("dafault")
        }
    }
    var sol = 0
    
    var slicedConverted = converted[converted.indices]
    
    while slicedConverted.isEmpty != true {
        let first = slicedConverted.popFirst()!
        
        if let second = slicedConverted.first {
            if first.rawValue < second.rawValue {
                sol += second.rawValue - first.rawValue
                slicedConverted.removeFirst()
                continue
            }
        }
        sol += first.rawValue
    }
    
    return sol
    }
}

배열의 순회를 최소 3회한다.

1. stringArray 선언

2. converted.append 반복문.

3. while문.

 

slicedConverted를 만드는 O()를 모르겠다. 다만, converted.indices는 배열의 subscripting이므로, 배열을 순회하는 것과 비슷한 동작으로 할 것으로 예상.

 

때문에, 최소한 O(3n)일 것. (3을 넣어도 되나..? 이러한 상수는 생략하는 것으로 기억하는데...)

고수의 발자취를 참고한 코드

class Solution {
    func romanToInt(_ s: String) -> Int {
    let roman : [Character:Int] = ["I":1,"V":5,"X":10,"L":50,"C":100,"D":500,"M":1000]
    var sol = 0, prev = 0
    
    s.forEach({
        let present = roman[$0] ?? 0
        
        if present > prev {
            sol += present - prev * 2
        } else {
            sol += present
        }
        prev = present
    })
    
    return sol
}
}

배열의 변환을 제거했다. 이를 대신하여, dictionary를 사용하여, 즉시 변환한다.

이전 값을 따로 저장하여, 현재 값과 비교하여 더할 값을 정한다.

sol += present - prev * 2

인 이유는, 이전 값을 이미 더했으므로, 그걸 뺴주고, 원래 더해야 할 값을 더하는 것.

ex) IV -> " I ", " V " ->
 첫번째 반복 : 0 + 1

 두번째 반복 : 1 + 5 - 1 * 2

 

ex) MCMXCIV -> " M ", " C ", " M ", " X ", " C ", " I ", " V " ->
 첫번째 반복 : 0 + 1000

 두번째 반복 : 1000 + 100

 세번째 반복 : 1100 + 900 - 100 * 2

 네번째 반복 : 1900 ....