[Python/BOJ] 2608. 로마 숫자

https://www.acmicpc.net/problem/2608

문제

로마 시대 때는 현재 사용하는 아라비아 숫자가 아닌 다른 방법으로 수를 표현하였다.

로마 숫자는 다음과 같은 7개의 기호로 이루어진다.

수를 만드는 규칙은 다음과 같다.

1. 보통 큰 숫자를 왼쪽에 작은 숫자를 오른쪽에 쓴다. 그리고 그 값은 모든 숫자의 값을 더한 값이 된다. 예를 들어 LX = 50 + 10 = 60 이 되고, MLI = 1000 + 50 + 1 = 1051 이 된다.
2. V, L, D는 한 번만 사용할 수 있고 I, X, C, M은 연속해서 세 번까지만 사용할 수 있다. 예를 들어 VV나 LXIIII 와 같은 수는 없다. 그리고 같은 숫자가 반복되면 그 값은 모든 숫자의 값을 더한 값이 된다. 예를 들어 XXX = 10 + 10 + 10 = 30 이 되고, CCLIII = 100 + 100 + 50 + 1 + 1 + 1 = 253 이 된다.
3. 작은 숫자가 큰 숫자의 왼쪽에 오는 경우는 다음과 같다. IV = 4, IX = 9, XL = 40, XC = 90, CD = 400, CM = 900 을 나타낸다. 이들 각각은 한 번씩만 사용할 수 있다. 그런데 IV 와 IX 는 같이 쓸 수 없으며 XL 과 XC, CD 와 CM 또한 같이 쓸 수 없다. 이들 외에는 작은 숫자가 큰 숫자 왼쪽 어디에도 나올 수 없다. 예를 들어 XCXC 나 CMCD, VX 나 IIX 와 같은 수는 없다. 참고로 LIX = 50 + 9 = 59, CXC = 100 + 90 = 190 이 된다.
4. 모든 수는 가능한 가장 적은 개수의 로마 숫자들로 표현해야 한다. 예를 들어 60 은 LX 이지 XLXX 가 아니고, 5 는 V 이지 IVI 가 아니다.

아래의 예를 참고 하시오.

• DLIII = 500 + 50 + 3 = 553
• MCMXL = 1000 + 900 + 40 = 1940
• 235 = CCXXXV
• 2493 = MMCDXCIII

로마 숫자로 이루어진 두 수를 입력받아 그 둘을 더한 값을 아라비아 숫자와 로마 숫자로 출력하는 프로그램을 작성하시오.

입력

첫째 줄과 둘째 줄에 하나씩 로마 숫자로 표현된 수가 주어진다. 입력된 각 수는 2000 보다 작거나 같고, 두 수의 합은 4000보다 작다.

출력

입력으로 주어진 두 수를 더한 값을 첫째 줄에 아라비아숫자로 출력하고 둘째 줄에는 로마 숫자로 출력한다.

풀이

Code

import sys
input = sys.stdin.readline

# 1. 아라비아 숫자 변환 함수 정의
def to_arabia(roma_num) :
    arabia = 0
    #1-1.
    while roma_num :
        # 1-1-1. 왼쪽 문자 추출
        string = roma_num.pop(0)
        # 1-2-1. 해당 문자가 I, X, C일 경우
        if string in ["I", "X", "C"] :
            # 다음 문자랑 합한 결과가 IV, IX, XL, XC, CD, CM 중에 있을 경우
            if roma_num and string + roma_num[0] in ["IV", "IX", "XL", "XC", "CD", "CM"] :
                # 왼쪽 문자 한 번 더 추출
                string += roma_num.pop(0)
        # 1-2-3. 출력 값 업데이트
        arabia += roma2arabia[string]
    # 1-3. 숫자 반환
    return arabia
# 2. 두 로마 숫자 사용 가능여부 함수 정의
def check(num) :
    # 2-1. 상반되는 문자를 사용한 적이 있는 경우
    if counter[conflicting_characters[num]] == 0 :
        return False
    # 2-2. 이외의 경우
    else :
        return True
# 3. 문자 카운트 함수 정의
def counting(num, cnt) :
    # 3-1. 주어진 문자 감소
    counter[num] -= cnt
    # 3-2. 2글자짜리 수인 경우 처리
    if len(num) == 2 :
        for n in num.split() :
            counter[n] -= 1
# 4. 로마 숫자 변환 함수 정의
def to_roma(arabia) :
    roma = ""
    # 4-1.
    for key, value in roma2arabia.items() :
        # 4-1-1. 남은 수를 현재 아라비아 수로 나눈 몫이 0보다 클 때
        if arabia // value > 0 :
            # 현재 로마 숫자가 2글자인 경우
            if len(key) == 2 :
                # 사용 불가능할 경우 continue
                if not check(key) : continue
            # 로마 숫자 업데이트
            # 남은 수 업데이트
            if arabia // value >= counter[key] :
                roma += key * counter[key]
                arabia -= value * counter[key]
                counting(key, counter[key])
            else :
                cnt = arabia // value
                roma += key * cnt
                arabia -= value * cnt
                counting(key, cnt)
            # 남은 수가 없다면 break
            if arabia == 0 : break
    # 4-2. 로마 숫자 반환
    return roma

roma_num1, roma_num2 = list(input().rstrip()), list(input().rstrip())

# 5. 로마-아라비아 딕셔너리 생성
roma2arabia = {"M" : 1000, "CM" : 900, "D" : 500, "CD" : 400, "C" : 100,
               "XC" : 90, "L" : 50, "XL" : 40, "X" : 10,
               "IX" : 9, "V" : 5, "IV" : 4, "I" : 1}
# 6. 상반되는 문자 딕셔너리 생성
conflicting_characters = {"IV" : "IX", "IX" : "IV",
                          "XL" : "XC", "XC" : "XL",
                          "CD" : "CM", "CM" : "CD"}
# 7. 카운터 딕셔너리 생성
counter = {"V": 1, "L": 1, "D": 1,
           "I": 3, "X": 3, "C": 3, "M": 3,
           "IV" : 1, "IX" : 1, "XL" : 1, "XC" : 1, "CD" : 1, "CM" : 1}
# 7. 아라비아 숫자 구하기
ans_arabia = to_arabia(roma_num1) + to_arabia(roma_num2)
# 8. 로마 숫자 구하기
ans_roma = to_roma(ans_arabia)
# 9. 결과 출력
print(f"{ans_arabia}\n{ans_roma}")