Integer to Roman

Q: 정수를 로마 숫자로 변환하는 시간 복잡도는 얼마인가요?

O(1) . 입력은 최대 3999이므로 탐욕적 루프는 표의 13개 행을 확인하고 기호를 최대 15개 추가합니다. 더 큰 숫자가 허용되고 반복된 M 으로 작성된다면, 시간은 num / 1000 에 따라 증가합니다.

Q: 값을 반복하는 루프 없이 정수를 로마 숫자로 변환할 수 있나요?

네. 각 자릿수에 해당하는 문자열을 표에 저장하세요. 예를 들어 백의 자리에는 "" , C , CC , CCC , CD , D , DC , DCC , DCCC , CM 을 사용합니다. num 의 각 자릿수를 조회한 뒤 문자열을 이어 붙이세요. 저장하는 문자열은 34개이며, 시간 복잡도는 O(1) 입니다.

Q: 3999가 허용되는 가장 큰 숫자인 이유는 무엇인가요?

M 는 가장 큰 문자이며 어떤 문자도 연속해서 네 번 나타날 수 없으므로, 천 단위는 MMM 까지이고 3999는 MMMCMXCIX 입니다. 더 큰 수는 문자 위에 막대를 그어 1000을 곱하는 것과 같은 추가 기호를 사용해 표기했습니다.

보통수학과 시뮬레이션 그리디

+10

로마 숫자는 일곱 개의 문자로 이루어져 있습니다. M은 1000, D는 500, C는 100, L은 50, X는 10, V는 5, I는 1입니다. 문자는 큰 수부터 작은 수 순서로 나열해 더하므로 7은 VII입니다. 같은 문자를 연속해서 네 번 반복하지 않습니다. 4, 9, 40, 90, 400, 900은 각각 IV, IX, XL, XC, CD, CM으로 씁니다. 이는 작은 문자를 그 뒤에 오는 큰 문자에서 빼는 방식입니다. 작은 문자를 먼저 쓰는 조합은 이 여섯 쌍뿐입니다.

정수 num이 주어지면 로마 숫자로 반환하세요.

함수

intToRoman(num: integer) → string

numinteger: 1부터 3999까지의 정수
반환값string: num에 해당하는 로마 숫자(대문자)

제약 조건

1 ≤ num ≤ 3999

예제

입력: num = 49
출력: "XLIX"
설명: 49는 40 + 9이므로 숫자는 XL 다음에 IX가 옵니다: XLIX. IL은 허용되지 않습니다. I는 IV와 IX에서만 빼기 때문입니다.

입력: num = 2026
출력: "MMXXVI"
설명: 2026에는 숫자 4나 9가 없으므로 쌍이 필요하지 않으며, 문자의 값을 더하면 1000 + 1000 + 10 + 10 + 5 + 1은 MMXXVI입니다.

입력: num = 944
출력: "CMXLIV"
설명: 944는 900 + 40 + 4이며, 각 부분은 뺄셈 쌍입니다. CM, XL, IV를 결합하면 CMXLIV가 됩니다.

후속 질문

문자열이 주어졌을 때, XLIX는 허용하고 IIII, IL, VX는 거부하는 표준 형식의 로마 숫자인지 확인할 수 있나요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

6개의 뺄셈 쌍을 각각 독립된 기호로 알파벳에 추가하면, 숫자를 쓰는 일은 거스름돈을 만드는 것과 같아집니다. 항상 들어맞는 가장 큰 값을 선택하세요. 입력값은 최대 3999이므로 작업량은 일정하게 적습니다.

덧셈 형태로 쓴 다음 긴 형태를 줄이세요

핵심 아이디어

처음에는 쌍을 무시하세요. 들어갈 수 있는 만큼 M을 쓴 다음 D를 쓰고, 이런 식으로 I까지 내려갑니다. 944의 경우 DCCCCXXXXIIII가 됩니다. 이 덧셈식 표기법은 숫자가 4나 9인 경우에만 표준 표기법과 다르며, 그런 자리는 항상 짧은 형태가 있는 다음 여섯 문자열 중 하나입니다. DCCCC는 CM이고, CCCC는 CD이며, LXXXX는 XC이고, XXXX는 XL이며, VIIII는 IX이고, IIII는 IV입니다.

DCCCC를 CCCC보다 먼저 바꾸세요. 그렇지 않으면 900이 DCD가 됩니다. 십의 자리와 일의 자리에서도 마찬가지입니다. 덧셈식 표기법은 글자가 최대 18개(3999)이므로, 작업량은 O(1)이며 두 번째 순회와 몇 개의 임시 문자열이 필요합니다.

알고리즘

M부터 I까지 일곱 글자 각각에 대해, num이 해당 값 이상인 동안 그 글자를 덧붙이고 매번 해당 값을 뺍니다.
DCCCC를 CM으로 바꾼 다음, CCCC를 CD로 바꿉니다.
LXXXX를 XC로 바꾼 다음, XXXX를 XL로 바꿉니다.
VIIII를 IX로 바꾼 다음, IIII를 IV로 바꿉니다.
문자열을 반환합니다.

def intToRoman(num):
    letters = [(1000, "M"), (500, "D"), (100, "C"), (50, "L"), (10, "X"), (5, "V"), (1, "I")]
    numeral = ""
    for value, letter in letters:
        while num >= value:
            numeral += letter
            num -= value
    # Each long form appears at most once; the longer one goes first.
    fixes = [("DCCCC", "CM"), ("CCCC", "CD"), ("LXXXX", "XC"),
             ("XXXX", "XL"), ("VIIII", "IX"), ("IIII", "IV")]
    for long_form, short_form in fixes:
        numeral = numeral.replace(long_form, short_form)
    return numeral

13개의 값에 대한 그리디

핵심 아이디어

일곱 개의 문자와 여섯 개의 쌍을 값의 내림차순으로 정렬합니다: 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. 들어맞는 가장 큰 값을 선택하는 것이 항상 옳습니다. 아래 자릿수의 모든 값은 그 위 자릿수의 가장 작은 값보다 작으므로, 루프는 다음 자릿수에 도달하기 전에 한 자릿수에서 끝납니다. 한 자릿수 안에서는 9, 5, 4, 1에 해당하는 값으로 각 숫자를 표준적인 방식으로 씁니다. 9는 9 기호, 5부터 8까지는 5 기호에 1 기호를 최대 세 개 더한 형태, 4는 4 기호, 1부터 3까지는 1 기호로 씁니다.

3746의 경우 루프는 MMM, D, CC, XL, V, I를 씁니다: MMMDCCXLVI. 표에는 행이 13개 있고 답은 최대 15글자이므로, 작업량은 한 번의 순회로 O(1)입니다.

알고리즘

1000부터 1까지의 13개 값을 기호와 함께 나열합니다. 쌍도 포함합니다.
빈 문자열로 시작합니다.
각 행에서 num이 해당 값보다 크거나 같은 동안 기호를 추가하고 값을 뺍니다.
모든 행이 끝나면 문자열을 반환합니다.

def intToRoman(num):
    values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
    symbols = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]
    parts = []
    for value, symbol in zip(values, symbols):
        while num >= value:  # take the largest value that still fits
            parts.append(symbol)
            num -= value
    return "".join(parts)

함정과 경계 사례

표에서 CM 앞에 D를 놓습니다. 그러면 900은 DCD가 됩니다.
각 행에서 while 대신 if를 사용합니다. 3000에는 M이 세 번 필요합니다. if를 사용하면 MCMDCDCXCX가 됩니다.
다른 쌍을 임의로 만들어 냅니다. 99는 IC가 아니라 XCIX이고, 45는 VL이 아니라 XLV입니다.
C에서는 버퍼가 너무 작을 수 있습니다. 가장 긴 결과인 3888의 경우 글자가 15개이므로 종료용 0을 포함해 16바이트가 필요하며, 덧셈식 표기에는 19바이트가 필요합니다.

자주 묻는 질문3

정수를 로마 숫자로 변환하는 시간 복잡도는 얼마인가요?

O(1). 입력은 최대 3999이므로 탐욕적 루프는 표의 13개 행을 확인하고 기호를 최대 15개 추가합니다. 더 큰 숫자가 허용되고 반복된 M으로 작성된다면, 시간은 num / 1000에 따라 증가합니다.

값을 반복하는 루프 없이 정수를 로마 숫자로 변환할 수 있나요?

네. 각 자릿수에 해당하는 문자열을 표에 저장하세요. 예를 들어 백의 자리에는 "", C, CC, CCC, CD, D, DC, DCC, DCCC, CM을 사용합니다. num의 각 자릿수를 조회한 뒤 문자열을 이어 붙이세요. 저장하는 문자열은 34개이며, 시간 복잡도는 O(1)입니다.

3999가 허용되는 가장 큰 숫자인 이유는 무엇인가요?

M는 가장 큰 문자이며 어떤 문자도 연속해서 네 번 나타날 수 없으므로, 천 단위는 MMM까지이고 3999는 MMMCMXCIX입니다. 더 큰 수는 문자 위에 막대를 그어 1000을 곱하는 것과 같은 추가 기호를 사용해 표기했습니다.

def intToRoman(num):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

테스트 #3

인자

num = 49

예상 출력

"XLIX"