[BOJ] 4531: Verdis Quo

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

BOJ - Verdis Quo

문제 유형 : 문자열 처리, 구현

문제 난이도 : Silver I

 

문제

로마인들은 알파벳의 일곱 문자를 통해서 수를 표현했다. 다음은 문자와 그에 대응하는 값을 보여주는 표이다.

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

이 7개의 숫자와 다음 규칙들을 통해서, 로마인들은 원하는 모든 수를 적을 수 있었다.

• 만약에 주어지는 숫자들이 감소순으로 좌에서 우로 적혀있다면, 덧셈법칙을 쓸 수 있다. 예를 들어, 로마숫자 MMCLVII는 1000 + 1000 + 100 + 50 + 5 + 1 + 1 = 2157이다.
• 이는 로마숫자를 지나치게 길게 하는 단점이 있어 뺄셈법칙 역시 존재한다. 만약에 왼쪽에 오른쪽에 있는 문자보다 작은 숫자가 적혀있다면, 왼쪽에 있는 수를 빼야한다. 예를 들어, 로마숫자 MCMXIV는 1000 − 100 + 1000 + 10 − 1 + 5 = 1914이다.
• I, X, C를 네번 이상 연달아 쓸 수 없다. IIII는 IV와 같은 더 짧은 꼴로 바꿔야 한다.
• V, L, D를 두번 이상 연달아 쓸 수 없다.
• M에 대해서는 제한이 없다.
• 뺄셈 법칙은 한개의 왼쪽 숫자에 대해서만 작동한다, 즉, IV는 4이지만, IIV는 3이 아니며 로마 숫자도 아니다.
• 뺄셈 법칙에 붙을 수 있는 왼쪽 숫자는 I, X, C 뿐이다.
• 뺄셈 법칙에서 I는 V / X 옆에만, X는 L / C 옆에만, C는 D / M 옆에만 올 수 있다.

이 규칙을 만족하는 로마숫자들이 주어질 때 이를 십진수 정수로 바꾸시오.

 

입력

첫 번째 줄에는 N이 주어진다. N은 변경할 로마 숫자의 수이다.

이후 N개의 줄에 로마숫자가 하나씩 주어진다. 로마숫자는 위에 적혀있는 규칙을 따르며 10000 이하의 자연수이다.

 

출력

주어지는 로마숫자를 10진수 정수로 바꾸어서 한 줄씩 출력하라.

 

풀이

LeetCode의 Roman to Integer와 같은 로직이다.

로마자 문자열을 순차적으로 읽으면서, 숫자로 변환해서 누적시키면 되는데, 만약에 뒤에 더 큰 로마자가 있다면, 빼기 연산을 대신 해주면 된다.

 

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

int roman_to_integer(string &s)
{
    unordered_map<char, int> values = {
        {'I', 1},
        {'V', 5},
        {'X', 10},
        {'L', 50},
        {'C', 100},
        {'D', 500},
        {'M', 1000}};
    int num = 0;
    for (int i = 0; i < s.length(); i++)
    {
        if (i + 1 < s.length() && values[s[i]] < values[s[i + 1]])
        {
            num -= values[s[i]];
        }
        else
        {
            num += values[s[i]];
        }
    }
    return num;
}

int main() {
    int n;
    cin >> n;

    vector<string> romans;
    string s;
    for (int i = 0; i < n; ++i)
    {
        cin >> s;
        romans.push_back(s);
    }

    for(auto &roman : romans) {
        cout << roman_to_integer(roman) << "\n";
    }

    return 0;
}