[LeetCode] Roman to Integer 파이썬 (dict, stack, deque)

from collections import deque
class Solution:
    def romanToInt(self, s: str) -> int:
        symbol = {"IV":4, "IX":9, "XL":40, "XC":90, "CD":400, "CM":900}
        roman = {"I":1,"V":5,"X":10,"L":50,"C":100,"D":500, "M":1000,
                "IV":4, "IX":9, "XL":40, "XC":90, "CD":400, "CM":900}

        stack = deque()
        stack.append((s[0],0))

        for i in range(1, len(s)):
            pattern = stack[-1][0]+s[i]

            if pattern in symbol:
                stack.pop()
                stack.appendleft((pattern,i))

            else:
                stack.append((s[i],i))

        answer = []
        for x in sorted(stack, key=lambda x:x[1]):
            if x[0] in roman:
                answer.append(roman[x[0]])
        return sum(answer)
        

deque에 tuple로 넣어서 sort

 

처음에 stack을 사용해야겠다고 생각은 했는데 순서를 해결할 방법이 생각이 안나서 고민하다가

양방향 queue인 deque를 사용해서 해결해야겠다고 생각

그리고 deque를 사용해도 입력 순서가 필요했기 때문에 tuple로 pattern과 순서(idx)를 함께 넣어줌

stack에는 string idx 순서대로 들어가고,

string pattern이 symbol이라는 dict에 있다면 해당 순서와 pattern을 함께 넣어줌

 

마지막으로 sorted를 사용해서 tuple의 1번째 idx 기준으로 sort 해준 deque의 key값을 찾고 해당 key값의 roman 숫자인 value를 answer 리스트에 삽입.

 

dict, tuple, deque, sort 모두 사용

 

정답안보고 해결한게 뿌듯하다

---

Runtime: 52 ms

Memory Usage: 14.2 MB