[LeetCode] 227. Basic Calculator II

말하는 감자·2024년 12월 12일

data structure leetcode python stack 리트코드 스택 자료구조 코딩테스트 코딩테스트 준비 파이썬

LeetCode

목록 보기

32/32

1. 오늘의 학습 키워드

Stack

2. 문제: 227. Basic Calculator II

단계: Medium
주제: Math, String, Stack
출처: https://leetcode.com/problems/basic-calculator-ii/description/

Description

Given a string s which represents an expression, evaluate this expression and return its value.

The integer division should truncate toward zero.

You may assume that the given expression is always valid. All intermediate results will be in the range of [-231, 231 - 1].

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

Example 1:

Input: s = "3+2*2"
Output: 7

Example 2:

Input: s = " 3/2 "
Output: 1

Example 3:

Input: s = " 3+5 / 2 "
Output: 5

Constraints:

1 <= s.length <= 3 * 105
s consists of integers and operators ('+', '-', '*', '/') separated by some number of spaces.
s represents a valid expression.
All the integers in the expression are non-negative integers in the range [0, 231 - 1].
The answer is guaranteed to fit in a 32-bit integer.

3. 문제 풀이

Step1. 문제 이해하기

문자열 s가 주어졌을 때, 이 문자열이 나타내는 수식을 계산하고 그 값을 반환하세요.

정수 나눗셈은 0을 향해 내림(truncation toward zero) 처리가 되어야 합니다.

주어진 수식은 항상 유효하다고 가정할 수 있습니다. 모든 중간 계산 결과는 [-2³¹, 2³¹ - 1] 범위에 포함됩니다.

주의: eval()과 같은 문자열을 수학적 수식으로 평가하는 내장 함수는 사용할 수 없습니다.

즉, 해당 문제의 값은 int형에 들어간다는 것을 의미하며, 문자열 내엔 ('+', '-', '*', '/') 4가지의 연산자가 있습니다. '/' 연잔자의 결과고 무조건 int형이 나와야 하기 때문에 내림처리를 해야 합니다.

입출력 및 제약 조건을 보도록 하겠습니다.

Input:
- 문자열 s 가 입력으로 주어집니다. 이 문자열의 길이는 1이상 3 * $10^5$ 이하입니다.
- 따라서 $O(n^2)$ 보다 효율적으로 시간 복잡도를 구성해야 합니다.
Output:
- 문자열이 나타내는 수식을 계산하고 그 값을 반환해야 합니다.
- 반환하는 값도 32-bit int자료형이라고 합니다.

Step2. 문제 분석하기

일반적으로 사칙연산은 왼쪽에서 오른쪽 방향순으로 이뤄지지만 '*', '/' 가 '+', '-' 보다 우선입니다. 따라서 '*', '/' 가 나온다면 이 연산자 전에 있던 숫자와 연산자 다음의 연산을 바로 수행해야 하는것입니다.

따라서 이것은 LIFO 원리에 적용됩니다. 즉, 스택 자료구조를 활용하는것입니다. 스택 자료구조에서 발생하는 연산인 push, pop모두 시간 복잡도가 O(1)입니다.

따라서, 문자열 s 를 순회하는데의 시간인 O(n)정도로 구현이 가능함을 알 수 있습니다.

그럼, 이제 코드를 설계해볼까요?

Step3. 코드 설계하기

문자열 s 는 두 가지 경우가 있습니다.

문자열 s 에 숫자가 나올 때
사칙연산자가 나올 때

숫자가 나오면 숫자 처리를 진행합니다. 숫자는 두 자리수가 올 수 도 있습니다. 이럴땐 각 자리숫자를 계산하여 숫자를 만듭니다.

그리고 그 다음 연산자가 나오면 연산자에 따라 숫자를 스택 자료구조에 push하면 될 것 같습니다.

기본적인 양의 정수는 +값이기 때문에 시작 연산자는 +로 설정합니다.

+, -는 그대로 왼쪽에서 오른쪽으로 진행하기 떄문에 스택 자료구조에 그대로 넣습니다.

하지만 *, /는 바로 반응을 해야합니다. 따라서 이 경우에는 스택 자료구조에 이전 정수 값을 꺼내서 계산한 결과 값을 스택 자료구조에 넣어야 합니다.

마지막으로 스택 자료구조에 있는 숫자들을 모두 합하면 정답이 도출됩니다.

Step4. 코드 구현하기

class Solution(object):
    def calculate(self, s):
        # https://leetcode.com/problems/basic-calculator-ii/submissions/1476667577
        """
        :type s: str
        :rtype: int
        """
        s = s.replace(' ','')
        n = len(s)
        sign = '+'
        stack = []
        num = 0

        for i, char in enumerate(s):
            if char.isdigit():
                num = num * 10 + int(char)
            
            if char in '+-*/' or i == n - 1:
                if sign == '+':
                    stack.append(num)
                elif sign == '-':
                    stack.append(-num)
                elif sign == '*':
                    stack.append(stack.pop() * num)
                else:
                    stack.append(int(stack.pop() / float(num)))

                sign = char
                num = 0
        return sum(stack)

코드 설명:
- 문자열 처리:
  - 주어진 문자열 s 에서 공백을 제거하여 불필요한 문자를 없앱니다.
  - 연산자와 숫자를 구분하며 순회합니다.
- 숫자 처리:
  - 숫자가 연속으로 나타날 경우, 이를 모두 합쳐 하나의 숫자로 만듭니다.
  - 예를 들어, 12는 1과 2를 처리해 12로 변환합니다.
- 연산자 처리:
  - 연산자가 나타나거나 문자열의 끝에 도달하면, 이전 연산자(sign)에 따라 스택에서 계산을 수행합니다:
    - +: 현재 숫자를 스택에 추가합니다.
    - -: 현재 숫자의 음수 값을 스택에 추가합니다.
    - *: 스택에서 가장 마지막 값을 꺼내 현재 숫자와 곱한 값을 다시 스택에 추가합니다.
    - /: 스택에서 가장 마지막 값을 꺼내 현재 숫자로 나눈 값을 다시 스택에 추가합니다.
      - 나눗셈은 정수로 변환하며, 파이썬에서 음수 처리 시 int(a / b)로 구현합니다.
- 결과 반환:
  - 문자열 순회가 끝난 뒤, 스택에 남아있는 값들을 모두 더해 최종 결과를 반환합니다.
시간 복잡도
- 문자열 순회:
  - 문자열 s 를 한 번 순회하면서 숫자와 연산자를 처리합니다. 이는 $O(n)$ 입니다.
- 스택 연산:
  - 스택의 pop 및 append 연산은 모두 $O(1)$ 입니다. 따라서 연산자 개수에 비례해 $O(n)$ 입니다.
- 최종 합산:
  - 스택의 모든 값을 합산하는 연산은 $O(n)$ 입니다.
  
  최종 시간 복잡도: $O(n)$
결과: https://leetcode.com/problems/basic-calculator-ii/submissions/1476667577

4. 마무리

이번 문제는 스택 자료구조를 활용해 사칙연산의 우선순위를 효율적으로 처리하는 방법을 학습할 수 있었습니다. 문자열을 순회하며 숫자와 연산자를 구분하고, +, - 연산은 스택에 값을 추가하고, *, / 연산은 즉시 계산 후 결과를 스택에 추가하는 방식으로 구현하였습니다. 이를 통해 $O(n)$ 시간 복잡도 안에서 효율적인 계산이 가능했습니다. 특히, 나눗셈의 음수 처리와 정수 변환 과정을 이해하는 데 도움이 되었고, Python에서 int(a / b)가 소수점을 내림 처리함을 명확히 확인할 수 있었습니다. 스택 자료구조의 활용성과 수식 계산 문제를 해결하는 기본 원리를 배운 유익한 문제였습니다.

전체 코드는 다음 링크에서 확인할 수 있습니다.

읽어주셔서 감사합니다!!

말하는 감자

할 수 있다

이전 포스트