LC224: Basic Calculator

작성일

https://leetcode.com/problems/basic-calculator

  • 단순한 문제는 아니었다. 지난번에도 똑같이 TO가 났었던것 같다.
  • 가장 큰 아이디어는 숫자를 미리 잘라놓을 필요가 없다는 것.. 숫자모드와 아닌 모드를 구별해서 진행하면 한번만 읽으면 된다.
  • 그리고 atoi는 무지 느리다. 쓰지말자.
  • 괄호로 잘라서 스택에 넣는 방식으로 하면 느리다.
  • 빨라질 수 있는 포인트는 괄호가 연산 순서에 영향이 없고, 부호에만 영향을 준다는 것을 눈치채는 것이다.

결국 아래는 살짝 모자란 풀이.. 더 좋은 방식을 생각해보자.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int calculate(string s) {
        int sum = 0, sign = 1, num = 0;
        s += ')';
        for(int i = 0; i < s.size(); i++) {
            if(s[i] == ' ') continue;
            if(isdigit(s[i])) {
                num = 10*num + (s[i]-'0');
            } else if (s[i] == '(') {
                int st = ++i, lv = 1;
                for(;lv != 0; i++) {
                    if(s[i] == '(') lv++;
                    if(s[i] == ')') lv--;
                }
                int n = calculate(s.substr(st,i-1-st));
                sum += sign * n;
                i--;
            } else if (s[i] == ')'|| s[i] == '+'|| s[i] == '-') {
                sum += sign * num;
                num = 0;
                sign = s[i] == '-' ? -1 : 1;
            }
        }
        return sum;
    }
};