[해쉬] 로마자 숫자로 변환하기 - 스위프트

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

Roman to Integer - LeetCode

 

 

 

1. 예전에 풀었던 풀이 이때는 해쉬가 뭔지도 몰랐었다. 🤣

import Foundation

class Solution {
    func romanToInt(_ s: String) -> Int {
        let romanTuple: [(Character, Int)] = [("M",1000), ("D",500), ("C",100), ("L",50),  ("X",10), ("V",5), ("I",1)]
        let sArr = Array(s)
        var out: [Int] = []

        
        for romanChar in sArr {
            for i in 0..<romanTuple.count {
                if romanChar == romanTuple[i].0 {
                    out.append(romanTuple[i].1)
                }
            }
        }
        
        for i in 1..<out.count {
            if out[i-1] < out[i] {
                out[i-1] = -out[i-1]
            }
        }
        
        return out.reduce(0, +)
    }
}

var input: String = "III"

 

내가 이걸 왜 튜플+배열로 했을까 ㅋㅋ

지금 생각해보면 로마자 찾으려면 배열 전부를 돌아야 되서 매우 비효율적인 방법(완전탐색)으로 풀었던 것 같다.

옛날에 푼 걸 보니까 많이 늘은 것 같기도 하다!! 🥸

 

 

2. 해쉬테이블을 이용해 풀어서 O(1) 로 해결한 방법이다.

import Foundation

var input: String = "III"

class Solution2 {
    func romanToInt(_ s: String) -> Int {
        var answer = 0
        let romanDictionary: [Character:Int] = ["I":1, "V":5, "X":10, "L":50, "C":100, "D":500, "M":1000]
        let sArr = Array(s)
        var allNumber = [Int]()
        
        for element in sArr {
            var number = Int(romanDictionary[element]!)
            
            if let queueLastNumber = allNumber.last {
                if queueLastNumber < number {
                     allNumber[allNumber.endIndex-1] = -queueLastNumber
                }
            }
            allNumber.append(number)
        }
        
        answer = allNumber.reduce(0, +)
        return answer
    }
}

print(Solution2().romanToInt(input))