M'S Blog

M'S Blog

WWDC20 student challenge Winner!

leetcode 224 - Basic Calculator

1 분 소요

문제

leetcode 224 - Basic Calculator 풀러가기

문제 분석

기본 원리는 stack을 사용해서, 그냥 값을 계속 넣어주다가 )를 만나면 ( 가 나올 때까지 pop을 하고, ( ) 사이의 식을 계산해서 넣어주는 것이다.

ex. 1+(2+3+5)+6

stack에 1 + ( 2 + 3 + 5 까지는 그냥 들어가고 )를 만나면 ( 일때까지 pop을 해서 ( ) 사이의 식인 2+3+5를 계산한다.

그리고 그 값을 다시 stack에 넣어서 1 + 10이 되게 한다.

문제 풀이(C++)

  1. 전체 코드

    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
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    class Solution {
    public:
        int calculate(string s) {
           
            vector<string> exp;
            string temp;
            
            for(int i=0;i<s.size();i++){
                if(s[i] == ' '){
                    continue;
                }
                
                switch(s[i]){
                     case'(':case')':case'+':case'-':
                        if(temp.size()>0){
                            exp.push_back(temp);
                            temp.clear();
                        }
                         temp.push_back(s[i]);
                         exp.push_back(temp);
                         temp.clear();
                         break;
                     default:
                         temp.push_back(s[i]);
                 }
               
            }
            if(temp.size()>0){
                exp.push_back(temp);
                temp.clear();
            }
            
            deque<string> d;
            
            for(int i=0;i<exp.size();i++){
     
                d.push_back(exp[i]);
                
                if(exp[i] == ")"){
                    d.push_back(parenCal(d));
                }
            }
            
            return stoi(calculating(d));
        }
        
        string parenCal(deque<string>& d){
            deque<string> temp;
            
            d.pop_back();
            
            while(1){
                string curr = d.back();
                d.pop_back();
                if(curr == "("){
                    break;
                }  
                temp.push_front(curr);
            }
     
            return calculating(temp);
        }
        
        string calculating(deque<string>& d){
            int num1 = stoi(d.front());
            d.pop_front();
            while(!d.empty()){
                string op = d.front();
                d.pop_front();
                int num2 = stoi(d.front());
                d.pop_front();
                if(op == "+"){
                    num1 = num1+num2;
                }else if(op == "-"){
                    num1 = num1-num2;
                }
            }   
            return to_string(num1);
        }
    };
    		cs
    • 8~31번째 줄 : 숫자가 1자리 숫자가 아닌 경우가 있을 수 있으므로 연속된 하나의 숫자로 보기 위해 string을 배열을 만든다.
      • 여기서 숫자를 구하는 방법은 ( ) + - 전까지는 임시로 string을 만들어 계속 그 뒤에 값을 붙여서 string을 만든고, ( ) + - 가 나오면 string 배열에 넣어줌.
      • 숫자를 만드는 방식은 이것 말고도, ( ) + - 가 나오기 전까지 몇번의 수가 있는지 세서 10의 배수를 곱해주는 방식도 있음.
    • 35~42번째 줄 : 위에서 만든 식을 표현하는 string 배열을 이용하여 )를 만나기 전까지는 deque에 계속 넣어준다. )를 만나면 ( ) 사이의 값을 계산해 준 뒤, 그 결과를 deque에 새로 넣는다.(위의 문제 분석에서는 stack을 사용한다고 했는데, 후의 caculating 함수에서의 편의를 위해 deque 사용)
    • 47~62번째 줄 : ( )사이의 값을 계산하기 위한 함수다. ( 가 나올 때 까지, main에서 만든 deque을 pop한다. 그리고, 그 pop한 값을 임시 deque에 넣어줘서 그 deque을 calculating 함수로 전달해준다. 이때 calculating에서는 앞에서 뒤로 계산을 진행함으로 temp에는 push_front를 넣어준다.
    • 64~78번째 줄 : 넘어온 deque은 숫자 연산기호 숫자 연산기호 숫자로 구성된다. 따라서 이를 이용하여 숫자와 연산기호를 구별하여 계산을 진행하고, 그 값을 반환한다.

    Runtime: 76 ms, faster than 20.45% of C++ online submissions for Basic Calculator.

    Memory Usage: 52.8 MB, less than 5.69% of C++ online submissions for Basic Calculator.






아직 배움의 과정에 있는 학생이니 내용에 부족한 점이 보이면 지적은 하되, 비난은 하지 말아주세요!!

댓글남기기

참고