12. Integer to Roman

Problem

Seven different symbols represent Roman numerals with the following values:

Symbol	Value
I	1
V	5
X	10
L	50
C	100
D	500
M	1000

Roman numerals are formed by appending the conversions of decimal place values from highest to lowest. Converting a decimal place value into a Roman numeral has the following rules:

If the value does not start with 4 or 9, select the symbol of the maximal value that can be subtracted from the input, append that symbol to the result, subtract its value, and convert the remainder to a Roman numeral.
If the value starts with 4 or 9 use the subtractive form representing one symbol subtracted from the following symbol, for example, 4 is 1 (I) less than 5 (V): IV and 9 is 1 (I) less than 10 (X): IX. Only the following subtractive forms are used: 4 (IV), 9 (IX), 40 (XL), 90 (XC), 400 (CD) and 900 (CM).
Only powers of 10 (I, X, C, M) can be appended consecutively at most 3 times to represent multiples of 10. You cannot append 5 (V), 50 (L), or 500 (D) multiple times. If you need to append a symbol 4 times use the subtractive form.
Given an integer, convert it to a Roman numeral.

Example 1:

Input: num = 3749
Output: "MMMDCCXLIX"
Explanation:
3000 = MMM as 1000 (M) + 1000 (M) + 1000 (M)
700 = DCC as 500 (D) + 100 (C) + 100 (C)
40 = XL as 10 (X) less of 50 (L)
9 = IX as 1 (I) less of 10 (X)
Note: 49 is not 1 (I) less of 50 (L) because the conversion is based on decimal places

Example 2:

Input: num = 58
Output: "LVIII"
Explanation:
50 = L
8 = VIII

Example 3:

Input: num = 1994
Output: "MCMXCIV"
Explanation:
1000 = M
900 = CM
90 = XC
4 = IV

Constraints:

• 1 <= num <= 3999

Solution

Problem

주어진 정수 num을 로마 숫자로 변환해야 함.
로마 숫자 규칙:
기본적으로 큰 숫자부터 작은 숫자를 차례로 나열하여 표현.
4, 9, 40, 90, 400, 900은 감산 표기법을 사용해야 함.
예: 4 → IV, 9 → IX, 40 → XL, 90 → XC, 400 → CD, 900 → CM
같은 기호가 연속으로 최대 3번까지만 나올 수 있음.

Constraints

1. 1 ≤ num ≤ 3999

• 입력값의 범위가 1부터 3999 사이이므로, M(1000)까지만 고려하면 됨.
• 따라서, 더 높은 숫자(예: 4000 이상의 경우)는 신경 쓸 필요 없음.

2. 시간 복잡도 고려

• 1부터 3999까지 변환하는 것이므로, O(log N) 또는 O(1) 해결이 가능.
• num이 3999여도 13개 이하의 로마 숫자만 필요함(MMMCMXCIX).
• 반복문 한 번으로 해결 가능한 방식이 효율적.

Methodology

1. Greedy Algorithm (O(1))

• 로마 숫자를 큰 값부터 차례대로 처리:
  • M(1000)부터 I(1)까지 값과 기호를 매칭한 리스트를 사전 정의.
• 큰 숫자부터 반복적으로 빼면서 결과 문자열에 추가:
  • 현재 숫자보다 작은 가장 큰 로마 숫자를 찾음.
  • 해당 값을 num에서 빼면서, 대응되는 로마 숫자를 결과에 추가.
• 이 방식은 큰 숫자부터 차례로 사용하기 때문에 항상 최적해(Greedy) 보장됨.

Code

시간/공간 복잡도 분석

• 시간 복잡도:
  • 숫자를 큰 값부터 나누면서 감소시키므로, num이 3999라도 13번 이하의 연산으로 해결됨.
  • 따라서, O(1) (상수 시간).
• 공간 복잡도:
  • 정해진 배열(고정 크기)을 사용하고, 문자열을 저장하는 정도이므로 O(1).

#include <iostream>
#include <vector>

using namespace std;

string intToRoman(int num) {
    // 1. 로마 숫자의 값과 기호를 큰 순서대로 정의
    vector<pair<int, string>> roman = {
        {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"}
    };

    string result = "";

    // 2. 큰 값부터 차례대로 num에서 빼면서 결과에 추가
    for (auto &[value, symbol] : roman) {
        while (num >= value) {
            num -= value;
            result += symbol;
        }
    }

    return result;
}

// 테스트 코드
int main() {
    cout << "1994 -> " << intToRoman(1994) << endl; // Expected: "MCMXCIV"
    cout << "58 -> " << intToRoman(58) << endl;     // Expected: "LVIII"
    cout << "3749 -> " << intToRoman(3749) << endl; // Expected: "MMMDCCXLIX"
    return 0;
}