Codewars 문제 풀이 : Roman Numerals Encoder

서론

C++ STD 무식쟁이 임베디드 개발자가 C++ STD 좀 해볼까 하고 codewars의 문제 풀이에 도전합니다.

문제

CodeWars: Roman Numerals Encoder

간단히 말해서 아라비아 숫자를 로마 숫자로 변경하는 문제입니다. 위키에 다음과 같은 테이블이 있습니다.
SymbolIVXLCDM
Value1510501005001,000
여기에 IV(4), IX(9), LX(40), XC(90), CD(400), CM(900) 만 추가하면 됩니다.

해결방안

보통 IV와 같은 문자를 만드는 방법을 고민하게 되는데 이런 간단한 문제에서는 그냥 배열로 나열해놓고 하나씩 대입해버리더군요. 그게 간단합니다.

자료구조

C에서는 그냥 struct 만들어서 array로 돌려버리면 끝이지만, STD 를 쓰기로 했으니 고민이 됩니다.

std::map

적합해보입니다. value에 따라서 symbol을 가져오면 되니까요. 초기화도 간단해서 좋네요.
    std::map<int, std::string> romanNumeric = {
        { 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" }
    };
하지만 문제가 있습니다. std::map은 입력 순서대로 시퀀셜한 list가 아닙니다. key로 정렬됩니다. 즉 초기화는 1000부터 했어도 loop를 돌려보면 1부터 나온다는거죠.
    typedef std::map<int, std::string>::iterator Itr;
    for (Itr itr = romanNumeric.begin(); itr != romanNumeric.end(); itr++) {
        int value = itr->first;
        std::string symbol = itr->second;
        std::cout << value << ":" << symbol << std::endl;
    }
결과:
1:I
4:IV
5:V
9:IX
10:X
40:XL
50:L
90:XC
100:C
400:CD
500:D
900:CM
1000:M
제가 원하는 결과가 아닙니다. 물론 거꾸로 Iterate 할 수 있지만, 영 마음에 들지 않습니다. 라고 쓰고 점심먹고 와서 생각해보니 그렇게 나쁜 방법은 아니네요. 초기화도 깔끔하게 되고 end부터 역 iterate 하면 되니까요.

std::list std::pair

pair를 만들어서 list에 순서대로 push_back 하는 간단한 방법입니다. map처럼 깔끔하게 초기화를 할 수 있는 방법은 모르겠습니다.
    typedef std::pair<int, std::string> roman_pair;
    std::list<roman_pair> romanNumeric;
    romanNumeric.push_back(std::make_pair(1000, "M"  ));
    romanNumeric.push_back(std::make_pair(900,  "CM" ));
    romanNumeric.push_back(std::make_pair(500,  "D"  ));
    romanNumeric.push_back(std::make_pair(400,  "CD"  ));
    romanNumeric.push_back(std::make_pair(100,  "C"  ));
    romanNumeric.push_back(std::make_pair(90,   "XC" ));
    romanNumeric.push_back(std::make_pair(50,   "L"  ));
    romanNumeric.push_back(std::make_pair(40,   "XL"  ));
    romanNumeric.push_back(std::make_pair(10,   "X"  ));
    romanNumeric.push_back(std::make_pair(9,    "IX" ));
    romanNumeric.push_back(std::make_pair(5,    "V"  ));
    romanNumeric.push_back(std::make_pair(4,    "IV"  ));
    romanNumeric.push_back(std::make_pair(1,    "I"  ));
깔끔한 초기화는 아니지만 개념적으로 이렇게 하려던 것이었으니 사용하기로 합니다.

알고리즘

딱히 알고리즘이라고 할만한게 있을까요? O(n^2) 이라 그다지 기분이 좋지는 않습니다. 좀 더 나은 알고리즘이 있나 Solution을 찾아봤지만 딱히 없네요.
    std::string s;
    bool found = false;
    do {
        found = false;
        for (roman_pair p : romanNumeric) {
            int value = p.first;
            std::string symbol = p.second;
            if (number >= value) {
                s.append(symbol);
                number -= value;
                found = true;
                break;
            }
        }
    } while(found);
    return s;

테스트

미리 작성해둔 gtest도 무난히 통과하고 codewars 테스트도 통과했습니다.
TEST(RomanNumeralsEncoderTest, HandlesPositiveInput)
{
    EXPECT_EQ(solution(1666) , "MDCLXVI");
    EXPECT_EQ(solution(182) , "CLXXXII");
    EXPECT_EQ(solution(1990) , "MCMXC");
    EXPECT_EQ(solution(1875) , "MDCCCLXXV");
}





댓글

이 블로그의 인기 게시물

WSL2 Ubuntu 20.04 및 네트워크 설정

리눅스 멀티코어를 사용하는 tar 압축/해제

WSL에 X-Window로 Terminator 설치하고 Minicom까지