파이썬으로 정수를 로마 숫자로 변환하는 프로그램 만들기

숫자 num이 주어졌을 때, 이를 이에 대응하는 로마 숫자(Roman Numeral)로 변환하는 문제를 생각해 봅시다. 로마 숫자는 아래와 같은 기호와 값을 사용합니다.

• "I" = 1
• "V" = 5
• "X" = 10
• "L" = 50
• "C" = 100
• "D" = 500
• "M" = 1000

로마 숫자의 기본 규칙과 특수 경우

일반적으로 로마 숫자는 값이 큰 기호부터 작은 기호 순서대로 왼쪽에서 오른쪽으로 배치되며, 전체 값은 모든 기호의 합으로 계산됩니다. 하지만 몇 가지 특수한 경우가 있습니다. 값이 작은 기호가 값이 큰 기호의 왼쪽에 위치하면, 큰 값에서 작은 값을 빼는 것을 의미합니다.

이러한 특수 경우의 예시는 다음과 같습니다.

• "I"가 "V" 앞에 오면 4
• "I"가 "X" 앞에 오면 9
• "X"가 "L" 앞에 오면 40
• "X"가 "C" 앞에 오면 90
• "C"가 "D" 앞에 오면 400
• "C"가 "M" 앞에 오면 900

또한 로마 숫자에는 다음과 같은 규칙도 있습니다.

• 어떤 기호도 3번 이상 반복될 수 없습니다.
• "V", "L", "D" 기호는 반복해서 사용할 수 없습니다.

예를 들어 입력이 n = 1520이라면 출력은 "MDXX"가 됩니다. "MDXX"는 1000 + 500 + 10 + 10 = 1520을 나타내기 때문입니다.

해결 접근 방법

이 문제는 다음 단계를 따라 해결할 수 있습니다.

• 결과 문자열 res를 빈 문자열로 초기화합니다.
• (값, 기호) 쌍을 담은 테이블을 내림차순으로 준비합니다. [(1000, "M"), (900, "CM"), (500, "D"), (400, "CD"), (100, "C"), (90, "XC"), (50, "L"), (40, "XL"), (10, "X"), (9, "IX"), (5, "V"), (4, "IV"), (1, "I")]
• 테이블의 각 쌍(cap, roman)에 대해 다음을 수행합니다.
  • d := num을 cap으로 나눈 몫
  • m := num을 cap으로 나눈 나머지
  • res := res + roman * d
  • num := m
• res를 반환합니다.

구현 예제

아래 파이썬 코드를 통해 더 자세히 이해해 보겠습니다.

def solve(num):
    res = ""
    table = [
        (1000, "M"),
        (900, "CM"),
        (500, "D"),
        (400, "CD"),
        (100, "C"),
        (90, "XC"),
        (50, "L"),
        (40, "XL"),
        (10, "X"),
        (9, "IX"),
        (5, "V"),
        (4, "IV"),
        (1, "I"),
    ]
    for cap, roman in table:
        d, m = divmod(num, cap)
        res += roman * d
        num = m

    return res

num = 1520
print(solve(num))

입력

1520

출력

MDXX

이 알고리즘은 값이 큰 단위부터 차례대로 몫만큼 기호를 붙여 나가는 그리디(Greedy) 방식입니다. 파이썬의 divmod() 함수를 활용하면 몫과 나머지를 한 번에 구할 수 있어 코드가 더욱 간결해집니다. 시간 복잡도는 상수 개수의 테이블 항목만 순회하므로 사실상 O(1)로 매우 효율적입니다.