[leetcode][13] Roman to Integer

문제 : leetcode.com/problems/roman-to-integer/

---

로마 문자를 숫자로 1:1 매칭하는 map을 하나 만든다.

문자열 s를 처음부터 탐색하면서 문자를 숫자로 바꾼 결과(let, value)를 stack에 넣는다.

만약 value가 1이 아니라면 바로전 값이 1, 10, 100인지 확인하고 그 값의 5, 10의 배수가 value와 맞는지 비교해야 한다.

이를 위해 바로 전 값을 stack의 top에서 가져온 뒤 판단한다.

만약 마이너스가 되는 경우라면 value에 top 값을 빼주면서 stack을 pop 해준다.

value를 적절히 갱신 후 stack에 push 한다.

 

문자열 s를 모두 탐색해서 stack을 다 채웠다면 stack의 모든 숫자를 더한 값이 정답이 된다.

시간복잡도는 N = |s|라 하였을 때, O(2N).

문자열 s를 한 번 탐색하는데 O(N). stack을 모두 탐색하는데 O(N).

---

소스코드 : github.com/fpdjsns/Algorithm/blob/master/leetcode/easy/13.%20Roman%20to%20Integer.cpp