Roman to Integer

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

두 접근 방식 모두 각 문자를 한 번씩 읽으므로, n 개의 문자로 이루어진 숫자의 시간 복잡도는 O(n) 입니다. 조회 테이블의 크기가 고정되어 있으므로 추가 공간 복잡도는 O(1) 입니다. 1부터 3999까지의 숫자는 최대 15개의 문자로 이루어지므로, 실제로 필요한 작업량은 매우 적습니다.

Q: 왜 다음 기호보다 작은 기호를 빼나요?

이렇게 여섯 가지 감산 쌍이 만들어집니다. IV , IX , XL , XC , CD , CM 에서는 작은 기호가 큰 기호 앞에 오며, 그 쌍의 값은 큰 기호의 값에서 작은 기호의 값을 뺀 것입니다. 첫 번째 기호의 값을 빼고 두 번째 기호의 값을 더하면 정확히 그 값이 되며, 유효한 숫자에서는 다른 어떤 위치에도 작은 기호가 큰 기호 앞에 오지 않습니다.

쉬움수학과 시뮬레이션 해싱

+10

로마 숫자는 일곱 개의 기호를 사용합니다. I = 1, V = 5, X = 10, L = 50, C = 100, D = 500, M = 1000입니다. 기호는 가장 큰 것부터 가장 작은 것 순서로 쓰고 더합니다. 단, 작은 기호가 먼저 나오고 큰 기호에서 그 값을 빼는 여섯 가지 감산 조합은 예외입니다. IV = 4, IX = 9, XL = 40, XC = 90, CD = 400, CM = 900입니다.

유효한 로마 숫자 s가 주어집니다. 이 숫자가 나타내는 정수를 반환하세요.

함수

romanToInt(s: string) → integer

sstring: 대문자로 된 유효한 로마 숫자
반환값integer: 숫자의 값, 1부터 3999까지

제약 조건

1 ≤ s.length ≤ 15
s에는 I, V, X, L, C, D 및 M 문자만 포함됩니다.
s는 1부터 3999까지의 값을 나타내는 유효한 로마 숫자입니다.

예제

입력: s = "XXVII"
출력: 27
설명: XX는 10 + 10이고, V는 5이며 II는 1 + 1이므로, 합계는 27입니다. 어떤 기호 뒤에도 더 큰 기호가 오지 않으므로 모든 기호를 더합니다.

입력: s = "CDXLIV"
출력: 444
설명: 이 숫자는 뺄셈 표기 쌍 세 개가 연속으로 나열된 것입니다. CD는 400, XL은 40, IV는 4이므로 444가 됩니다.

입력: s = "MCDXCII"
출력: 1492
설명: M은 1000, CD는 400, XC는 90, II는 2이므로 숫자는 1492입니다. 쌍과 단일 기호를 자유롭게 섞어 사용할 수 있습니다.

후속 질문

1부터 3999까지의 정수를 로마 숫자로 바꾸는 역방향 코드를 작성할 수 있나요?

힌트

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

3개 중 0개 열림

풀이

숫자 표기의 대부분은 단순한 합이므로, 문제의 핵심은 여섯 가지 뺄셈 쌍을 찾아내는 것입니다. 두 글자로 된 토큰으로 찾아보거나, 여섯 가지 모두에 적용되는 한 가지 규칙을 사용하면 됩니다. 즉, 오른쪽에 있는 기호보다 값이 작은 기호는 뺍니다. 어느 쪽이든 최대 15개의 문자를 한 번 훑으면 답을 구할 수 있습니다.

빼기 쌍을 토큰으로 읽기

핵심 아이디어

숫자 표기를 토큰의 나열이라고 생각해 보세요. 대부분의 토큰은 기호 하나로 이루어져 있고, 다음 여섯 개는 기호 두 개로 이루어져 있습니다: IV, IX, XL, XC, CD 및 CM. 문자열을 이 토큰들로 나눈 다음 각 토큰의 값을 더하면 숫자가 됩니다.

각 위치에서 먼저 다음 두 문자를 살펴보세요. 여섯 쌍 중 하나를 이루면 그 쌍의 값을 더하고 두 문자를 모두 건너뜁니다. 그렇지 않으면 기호 하나의 값을 더하고 한 문자만 건너뜁니다. MCDXCII는 M, CD, XC, I, I로 나뉩니다. 따라서 1000 + 400 + 90 + 1 + 1 = 1492입니다.

쌍인지 확인하는 작업이 먼저 이루어져야 합니다. XC의 X를 따로 읽으면 10을 더한 다음 100을 더하게 되어, 90이 아닌 110이 됩니다. 이 확인은 안전하기도 합니다. 올바른 숫자 표기에서 작은 기호가 큰 기호 바로 앞에 오는 경우는 이 여섯 쌍 중 하나뿐이므로, 찾은 모든 쌍은 실제 쌍입니다.

각 단계에서 문자 하나 또는 두 개를 처리하므로 반복문은 최대 15회 실행됩니다. 두 테이블의 크기는 고정되어 있으므로 추가 공간은 상수입니다.

알고리즘

여섯 쌍을 위한 표 하나와 일곱 개의 단일 기호를 위한 표 하나를 만드세요.
합계를 0으로 설정하고 인덱스 0에서 시작하세요.
인덱스의 두 문자가 쌍을 이루면 해당 쌍의 값을 더하고 인덱스를 2만큼 이동하세요.
그렇지 않으면 단일 기호의 값을 더하고 인덱스를 1만큼 이동하세요.
인덱스가 끝을 지나면 합계를 반환하세요.

def romanToInt(s):
    pairs = {"IV": 4, "IX": 9, "XL": 40, "XC": 90, "CD": 400, "CM": 900}
    singles = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
    total = 0
    i = 0
    while i < len(s):
        two = s[i:i + 2]
        if two in pairs:
            total += pairs[two]
            i += 2
        else:
            total += singles[s[i]]
            i += 1
    return total

각 기호를 다음 기호와 비교하세요

핵심 아이디어

여섯 쌍을 다시 살펴보세요. 모든 쌍에서 첫 번째 기호의 값은 두 번째 기호보다 작고, 쌍의 값은 두 번째 기호에서 첫 번째 기호를 뺀 값입니다. 따라서 쌍 표를 없애고 하나의 규칙을 사용할 수 있습니다. 기호의 값이 오른쪽 기호보다 작으면 그 값을 빼고, 그렇지 않으면 더합니다. CM은 -100 + 1000이 되어 900이며, 토큰을 읽어 계산한 값과 같습니다.

MCDXCII를 따라가 보세요. M 다음에는 더 작은 C가 오므로 1000을 더합니다. C 다음에는 더 큰 D가 오므로 100을 뺍니다. 합계는 900입니다. D를 더해 1400이 됩니다. X 다음에는 더 큰 C가 오므로 10을 뺍니다. 1390입니다. C를 더하면 1490입니다. 첫 번째 I 다음에는 같은 I가 오므로 이를 더해 1491이 됩니다. 마지막 I에는 이웃 기호가 없으므로 이것도 더해 1492가 됩니다.

비교 연산은 엄격한 미만이어야 합니다. 같은 기호가 이웃하면 항상 더하며, 이 때문에 II는 2이고 XX는 20입니다. 이 규칙이 올바른 이유는 토큰을 읽는 방식이 올바른 이유와 같습니다. 유효한 숫자에서는 뺄셈 쌍의 앞부분인 경우에만 작은 기호가 큰 기호 바로 앞에 옵니다.

각 문자를 한 번씩 살펴보고 누적 합계 하나만 유지하므로 시간 복잡도는 O(n)이고 추가 공간 복잡도는 O(1)입니다. 이 방식에는 일곱 기호의 값과 문자마다 한 번의 비교만 필요합니다.

알고리즘

일곱 기호 각각의 값을 저장합니다.
0에서 시작하는 누적 합계를 사용해 s의 인덱스를 반복합니다.
다음 기호가 존재하고 현재 기호보다 값이 크면 현재 값을 뺍니다.
그렇지 않으면 현재 값을 더합니다.
반복문이 끝난 후 합계를 반환합니다.

def romanToInt(s):
    values = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
    total = 0
    for i in range(len(s)):
        value = values[s[i]]
        # A symbol worth less than the one after it is subtracted, like the I in IV.
        if i + 1 < len(s) and value < values[s[i + 1]]:
            total -= value
        else:
            total += value
    return total

함정과 경계 사례

규칙은 간단하므로 실수는 규칙의 경계에서 발생합니다.

엄격히 작음 대신 작거나 같음을 사용하는 경우. 그러면 각 첫 번째 기호를 빼므로 II는 0이 되고 XX도 0이 됩니다.
마지막 문자에서 다음 기호를 읽는 경우. 그 위치에는 s[i+1]이 없습니다. 먼저 i+1이 길이보다 작은지 확인하고, 마지막 기호는 항상 더하세요.
토큰 버전에서 쌍보다 단일 기호를 먼저 시도하는 경우. 그러면 XC는 10 + 100 = 110으로 읽힙니다.
두 번째 기호에서만 쌍을 알아차리는 경우. IV의 I를 이미 더했다면 두 번 빼야 합니다. 1 + 5 - 2 × 1 = 4입니다. 다음 기호와 비교하면 이 보정이 필요하지 않습니다.
Lua와 R 문자열은 인덱스 1부터 시작하므로 마지막 기호는 #s 또는 nchar(s)에 있다는 점을 잊는 경우.

자주 묻는 질문3

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

두 접근 방식 모두 각 문자를 한 번씩 읽으므로, n개의 문자로 이루어진 숫자의 시간 복잡도는 O(n)입니다. 조회 테이블의 크기가 고정되어 있으므로 추가 공간 복잡도는 O(1)입니다. 1부터 3999까지의 숫자는 최대 15개의 문자로 이루어지므로, 실제로 필요한 작업량은 매우 적습니다.

왜 다음 기호보다 작은 기호를 빼나요?

이렇게 여섯 가지 감산 쌍이 만들어집니다. IV, IX, XL, XC, CD, CM에서는 작은 기호가 큰 기호 앞에 오며, 그 쌍의 값은 큰 기호의 값에서 작은 기호의 값을 뺀 것입니다. 첫 번째 기호의 값을 빼고 두 번째 기호의 값을 더하면 정확히 그 값이 되며, 유효한 숫자에서는 다른 어떤 위치에도 작은 기호가 큰 기호 앞에 오지 않습니다.

로마 숫자를 오른쪽에서 왼쪽으로 변환할 수 있나요?

네. 마지막 기호에서 첫 번째 기호까지 거꾸로 이동하면서, 오른쪽에 있는 이전 기호의 값을 기억하세요. 현재 기호의 값이 그 기호보다 작으면 빼고, 그렇지 않으면 더하세요. 반대쪽에서 본 왼쪽에서 오른쪽으로 읽는 방식과 같은 규칙입니다.

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

테스트 #1

테스트 #2

테스트 #3

인자

s = "XXVII"

예상 출력