Roman to Integer
문제 : https://leetcode.com/problems/roman-to-integer/
입력 스트링에서 각 char가 앞의 char보다 값이 작다면 빼주되 그 외의 경우들은 더해가는 형식을 한다.
두 가지의 접근
1. 로마자 하나 씩
입력 string에 존재하는 문자 하나씩 읽고 해당 값을 읽어낸다.
만약 해당 문자의 값이 앞 문자의 값보다 작으면 전체 sum에서 뺄셈을
그 외는 덧셈을 한다.
convert라는 함수를 제작하여 사용
unordered_map 사용
해시함수를 사용하는 것을 볼 수 있다.unordered_map을 사용한 것이 훨씬 빨랐다.
2. IV는 4, IX는 9
문제에서 나오는 조건문이다. 즉, 4,9,40,90,400,900을 제외한 숫자의 표기들은 사실상 나오는 순서대로 더하면 된다는 것이다.
예를 들어, LVIII은 58(L = 50, V = 5, I = 1 - 순서대로 덧셈)이다. 하지만 XLVII은 47(XL = 40, VII = 7)인 것이다.
결론 : 위와 같은 숫자들을 따로 판별할 수 있다면 덧셈만으로 계산을 해낼 수 있다.
출처 : https://f-lab.kr/blog/how-good-algorithmic-solution
나는 해당 문제를 두개의 다른 dictionary를 사용하여 해결 하였다. 만약, 2개가 부족하다면 다른 언어(한자, 한글, 등등)에 적용시에는 더 늘리도록 해야겠다.
하지만 현저히 속도가 느린 것을 볼 수 있었다.
