본문으로 건너뛰기

2608 - 로마 숫자

info
  • 문제 보기: 2608 - 로마 숫자
  • 소요 시간: 💥1시간 초과
  • 풀이 언어: python
  • 체감 난이도: 3️⃣
  • 리뷰 횟수: ✅

풀이 키워드​

스포주의

빡구현 문자열


풀이 코드​

info
  • 메모리: 31252 KB
  • 시간: 36 ms
import sys
input = sys.stdin.readline

data_1w = dict({'I':1, 'V':5, 'X':10, 'L':50, 'C':100, 'D':500, 'M':1000})
data_2w = dict({'IV':4, 'IX':9, 'XL':40, 'XC':90, 'CD':400, 'CM':900})

def decode(a):
    i, res = 0, 0
    while i < len(a)-1:
        key = a[i] + a[i+1]
        if key in data_2w:
            res += data_2w[key]
            i += 1
        else:
            res += data_1w[a[i]]
            
        i += 1
    
    if i != len(a):
        res += data_1w[a[-1]]
    return res

def encode(b):
    res = ''
    while b > 0:
        if b >= 1000:
            res += 'M'
            b -= 1000
        elif b >= 900:
            res += 'CM'
            b -= 900
        elif b >= 500:
            res += 'D'
            b -= 500
        elif b >= 400:
            res += 'CD'
            b -= 400
        elif b >= 100:
            res += 'C'
            b -= 100
        elif b >= 90:
            res += 'XC'
            b -= 90
        elif b >= 50:
            res += 'L'
            b -= 50
        elif b >= 40:
            res += 'XL'
            b -= 40
        elif b >= 10:
            res += 'X'
            b -= 10
        elif b >= 9:
            res += 'IX'
            b -= 9
        elif b >= 5:
            res += 'V'
            b -= 5
        elif b >= 4:
            res += 'IV'
            b -= 4
        elif b >= 1:
            res += 'I'
            b -= 1
    return res

def solution():
    global data_key, data_val
    a = input().rstrip()
    b = input().rstrip()
    
    res1 = decode(a) + decode(b)
    print(res1)
    print(encode(res1))


if __name__ == '__main__':
    solution()

풀이 해설​

문자열 패턴의 특징에 따라 다르게 처리하는 것이 관건인 문제이다.

크게 2가지로 나뉠 수 있다.

  1. 그냥 한 글자 단위로 처리되는 경우
  2. IX 같이 두 글자 단위로 처리되는 경우

📌 Decode​

while i < len(a)-1:
    key = a[i] + a[i+1]
    if key in data_2w:
        res += data_2w[key]
        i += 1
    else:
        res += data_1w[a[i]]
        
    i += 1

그리고 이 파트는 글자 단위에 따라 나누어 처리하는 core 로직이다.

일부러 인덱스를 문자열의 끝까지 도는 것이 아니라, 한 칸 덜 순회하고

두 글자 단위 처리에서는 i를 2번, 한 글자 단위 처리에선 1번 옮긴다.

따라서 문자열이 두 글자 단위 처리로 순회 종료할 시, 해당 시점의 i값은 len(a)가 되고

한 글자 단위 처리로 종료할 시엔 len(a)-1이 된다.

if i != len(a):
    res += data_1w[a[-1]]

그러므로, 한 글자 단위 처리에선 마지막 인덱스의 문자를 처리하지 않았으니 a[-1] 요소에 대하여 조건부로 처리해준다.

📌 Encode​

큰 단위부터 우선으로 처리하고, 9 또는 4로 시작하는 구간의 케이스를 고려하여 조건을 잘~ 나누면 된다

단, 결과 값을 단위별로 숫자 분리해서 처리하는 로직은 WA를 받으니 이 방식으로 접근하면 안된다.


메모​

  • decode는 비교적 구현이 쉬운데, encode는 완전 하드코딩해야 해서 느낌이 별로였던 문제
  • encode 부분이 약간 그리디 동전문제와 비슷하다는 생각이 든다. (최소한의 동전 개수로 거슬러주기)