[LeetCode] 13 Roman to Integer - Python

Disclaimer: 배워가면서 정리하고 있습니다. 개념에 오류가 있을 수 있습니다.

1. 문제 이해하기 (클릭하면 문제로 이동)

문제 이해가 핵심인 문제다. 문제를 이해 하고나면(한참걸림) 코드 자체는 쉬워지는 매직! 문제를 잘 뜯어보자.

• 일단 입력값으로 s라는 문자열을 받는다. s는 로마 숫자로 I, V, X, L C, D, M으로 구성되어 있다.
• 출력은 int로 나온다.

여기까지 보면 별로 어려울게 없다. 하지만 문제는 감산표기(Subtractive Notation)를 이해하는 것이다. 원래 로마 숫자 특성상 LV=55처럼 큰 수가 왼쪽에 오는게 정석이다. 하지만 감산표기가 되는 경우는 작은 값이 왼쪽에 온다. 그리고 다음과 같은 6가지 경우가 있다.

• IV=4 (5-1)
• IX=9 (10-1)
• XL=40 (50-10)
• XC=90 (100-10)
• CD=400 (500-100)
• CM=900 (1000-100)

자 이제 로마 숫자를 받아서 읽기만 하면 된다. 로마 숫자를 읽는 방법은 크게 두 개다.

• 왼쪽에서 오른쪽으로 읽는 방법.
• 오른쪽에서 왼쪽으로 읽는 방법.

왼→오로 보다가 지금 값 < 다음 값이면 빼고, 아니면 더하면 된다. 혹은 오→왼으로 보며 이전(바로 오른쪽) 값보다 크면 더하고, 작거나 같으면 빼지 않고 더한다(구현 방식에 따라 반대로 처리). 이렇게 대부분 외국 유튜브에 나와있는 두 가지 방법이 있고, 그리고 G 선생님께 여쭤봐서 얻은 또 하나의 해법은 허용되는 감산 조합을 미리 지정하는 방법이다. 감산 규칙을 눈에 보이게 코드 안에 정리해 두니 가독성이 좋아진다.

예시:

2. 답 도출 방법

앞서 말한대로 이 문제에서 답을 도출하는 방법에는 크게 3가지가 있다. 왼오방법, 오왼방법 그리고 파싱방법. G선생님께서는 몇가지 더 있다고 하셨는데, 내가 그걸 알아듣기에는 초보라서 이해가 되지 않았다. 유튜브를 보면 대부분 오왼방법을 많이 쓰는 것 같다. 하나씩 구체적으로 살펴보자.

1. 왼오방법

가장 직관적이고 초보자에게 친절한 방법이다.

def romanToInt(s: str) -> int: 
    # val = {...} : 각 로만 문자가 어떤 수를 의미하는지 딕셔너리에 저장한다. 
    val = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}

    # ans = 0 : 답의 시작은 0부터, 0에서 부터 왼쪽 수를 더하는게 기본 값이다. 그러다가 i+1 값이 존재하고 i의 값보다 작으면 뺀다. 
    ans = 0 

    # 문자열을 왼쪽부터 한 글짜씩 본다. 
    for i in range(len(s)):

    # len(s) 보다 작은 i+1이 존재하면 (마지막 글짜가 아니면)그 인덱스의 값이 다음 글자보다 작은지 보고, 작으면 감산규칙 적용
        if i+1 < len(s) and val[s[i]] < val[s[i+1]]:
            ans -= val[s[i]]

    # 그 외에는 더한다.
        else: 
            ans += val[s[i]]

    # 그렇게 range(len(s))를 다 돌면 빼고 더한 값을 ans로 리턴
    return ans

복잡도

• 시간: O(n) 문자열길이 n
• 공간: O(1) 고정 크기 딕셔너리만 사용

장점

• 구현이 매우 간단하다.
• 추가 자료구조가 거의 없다(딕셔너리만 사용).

단점

• 인덱스 표기에서 실수할 가능성이 높음 (초보기준)

2. 오왼방법

전체적으로 for 문으로 문자열을 돌린다는 것에서는 왼오방법과 같다. 하지만 이 방법의 장점은 인덱스를 크게 생각하지 않아도 된다는 점이다. 그래서 조건이 좀 더 깔끔하게 보인다.

def romanToInt(s: str) -> int: 

    # val = {...} : 각 로만 문자가 어떤 수를 의미하는지 딕셔너리에 저장한다. 
    val = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}

    # ans = 0 : 여기서는 누적 합을 더할 변수다.
    ans = 0 

    # 오른쪽(이전) 문자의 값을 저장하는 변수다. 
    prev = 0 

    # 문자열을 reverse로 순회한다 (오른쪽 -> 왼쪽) 
    # 그리고 그 값을 value라는 변수로 하나씩 반환
    for ch in reversed(s): 
        value = roman[ch] 

        # prev에 저장된 값이 value에 저장된 값 보다 더 크면 감산 
        if value < prev: 
            ans -= value 
        # 그렇지 않으면 더한다.
        else:
            ans += value 

        # 다음 반복을 위해 prev 값을 지금 자리 value로 갱신해주고 다시 for 문으로 돌아간다. 
        prev = value

     #for 문 다 돌아서 ch가 하나씩 다 value에 들어갔다 나왔으면, ans 종료. 
     return ans

복잡도

• 시간: O(n) 문자열길이 n
• 공간: O(1) 고정 크기 딕셔너리만 사용

장점

• 경계 처리가 깔끔하다(다음 인덱스 체크가 없다).
• 직관적 조건(value < prev) 한 줄로 감산 여부가 결정된다

단점

• 문자열을 뒤집어 본다는 점이 처음엔 익숙하지 않을 수 있다(나도 reversed에 익숙치 않아서 왼->오를 선택)

3. 감산 우선확인 방법

감산 조합(IV, IX, XL, XC, CD, CM)을 두 글자 단위로 먼저 인식하고, 아니면 한 글자씩 처리하는 방식이다. 파서를 만드는 느낌이라 약간 더 포멀하다. 파싱은 문자열을 왼쪽부터 읽으면서 규칙에 맞는 토큰을 하나씩 떼서 값으로 바꾸고 인덱스 i를 앞으로 밀어가며 누적하는 과정이다. 이 방법에서 규칙은 하나, 항상 두 글자 조합을 먼저 확인하고, 매칭되면 인덱스를 2칸 이동, 아니면 한글자만 쓰고 인덱스를 1칸 이동하는 것이다. 흐름을 그림으로 보면 다음과 같다.

예시: MCMXCIV 

s = M C M X C I V  
i = 0 1 2 3 4 5 6

# i=0: s\[0:2\] = "MC" → pair에 없음 → M=1000 더하고 인덱스 하나 이동 i += 1 (i=1)
# i=1: s\[1:3\] = "CM" → pair에 있음 (900) → +900, 더하고 인덱스 두 개 이동 i += 2 (i=3)
# i=3: s\[3:5\] = "XC" → pair에 있음 (90) → +90 더하고, 인덱스 두 개 이동, i += 2 (i=5)
# i=5: s\[5:7\] = "IV" → pair에 있음 (4) → +4 더하고, 인덱스 두 개 이동, i += 2 (i=7 종료)

누적: 1000 + 900 + 90 + 4 = 1994

def romanToInt(s: str) -> int: 

    # 한글자 조합과 감산조합을 분리해서 딕셔너리로 저장
    single = {'I': 1, 'V': 5, 'X': 10, 'L': 50,'C': 100, 'D': 500, 'M': 1000}
    pair = {'IV': 4, 'IX': 9,'XL': 40, 'XC': 90, 'CD': 400, 'CM': 900}

    # 인덱스를 0부터 직접 움직인다. 

    i = 0 
    ans = 0 
    n = len(s) 

    # 문자열을 왼 -> 오른쪽으로 훑는다. 
    while i < n 

    # 현재 위치에서 pair가 보이면 그 값을 더하고 인덱스를 2 증가한다. 
        if i + 1 < n and s[i:i+2] in pair: 
            ans += pair[s[i:i+2]
            i += 2

    # pair가 아니고 single에 있으면 인덱스는 1만 증가한 후 그 값을 더한다. 
         else: 
             ans += single[s[i]]
            i+= 1 
       return ans 

 

 

복잡도

• 시간: O(n) (각 문자는 한 번만 소비됨)
• 공간: O(1) (고정 테이블)

장점

• “두 글자 감산 먼저”라는 규칙을 코드로 명시해 가독성이 좋다.
• 파싱 관점에서 확장/검증 로직을 붙이기 쉽다.

단점

• 테이블이 둘로 나뉘어 코드가 길어지고, 인덱스 관리에 실수할 여지가 있다.

 

3. 주요 개념: else의 생략에 관하여...

 

부트캠프에서 else가 생략 가능하다(조금 더 구체적으로 말하면 웬만하면 생략해라)라고 배워서... else가 생략이 가능한 줄 알았는데, 그게 아니었다. else가 필요한 경우와 필요하지 않는 경우가 따로 있었다.

• Else가 꼭 필요한 경우 

조건문이 참일 때와 거짓일 때 서로 다른 동작을 해야하는 경우. 즉 두 경우가 베타적일 때 else는 필수다. 조건이 거짓일 때 실행되지 말아야 하는 코드가 있는데 else 없이 그냥 쓰면 조건과 상관없이 항상 실행이 된다? 그럴 경우 else가 반드시 필요하다. 

 

• Else 생략이 가능한 경우

조건이 참일 때만 처리를 하고 저깃일 때는 아무것도 안 해도 되는 경우. 즉 조건 충족 시 추가 동작만 필요하다면 else는 생략 가능하다. 

 

그러니까 결론은, else를 생략할 수 있는 경우가 따로 있다!! 

 

4. 참고자료 

https://youtu.be/3jdxYj3DD98?si=1FqCiSXleL0UlTEW

 

https://www.youtube.com/watch?v=JlVOzbOJiv0