Codewars 문제 풀이 : Roman Numerals Encoder
서론
C++ STD 무식쟁이 임베디드 개발자가 C++ STD 좀 해볼까 하고 codewars의 문제 풀이에 도전합니다.문제
CodeWars: Roman Numerals Encoder간단히 말해서 아라비아 숫자를 로마 숫자로 변경하는 문제입니다. 위키에 다음과 같은 테이블이 있습니다.
여기에 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");
}
댓글
댓글 쓰기