문제 소개
간단한 수식 문자열을 평가하는 기본 계산기를 구현하는 것이 목표입니다. 입력 문자열에는 음수가 아닌 정수, 연산자(+, -, *, /), 그리고 공백만 포함되며, 정수 나눗셈은 몫(quotient)만 결과로 취합니다.
예를 들어 입력이 "3+2*2"라면 곱셈이 우선 수행되므로 출력은 7이 됩니다.
알고리즘 접근 방식
이 문제는 스택(Stack) 자료구조를 활용하면 깔끔하게 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 곱셈(*)과 나눗셈(/)을 만나면 즉시 직전 숫자와 연산하여 스택 최상단(top) 값을 갱신합니다.
- 뺄셈(-)은 다음 숫자를 음수로 변환해 스택에 저장합니다.
- 마지막에 스택에 남아 있는 모든 값의 합이 곧 최종 결과가 됩니다.
단계별 풀이 과정
- 스택 s, 인덱스 i := 0, 공백 제거용 문자열 x := ""를 초기화합니다.
- 입력 문자열의 각 문자 j를 순회하며 공백이 아닌 문자만 x에 추가합니다.
- s := x로 갱신하고, n := len(x)를 설정합니다.
- i < n인 동안 아래를 반복합니다.
- s[i] == '/' (나눗셈): i를 1 증가시킨 후, i번째 인덱스부터 시작하는 숫자 num을 읽고 i를 해당 숫자의 마지막 위치로 갱신합니다. 스택 최상단 값이 음수라면 -(절댓값 / num)으로, 양수라면 (값 / num)으로 갱신합니다.
- s[i] == '*' (곱셈): i를 1 증가시킨 후 숫자 num을 읽고, 스택 최상단 값에 num을 곱해 갱신합니다.
- s[i] == '-' (뺄셈): i를 1 증가시킨 후 숫자 num을 읽고, -num을 스택에 push합니다.
- s[i] == '+' (덧셈): i를 1 증가시킨 후 숫자 num을 읽고, num을 스택에 push합니다.
- 그 외 (숫자): 숫자 num을 읽어 스택에 push합니다.
- 반복이 종료되면 스택 요소들의 합을 반환합니다.
나눗셈에서 음수를 특별히 처리하는 이유
나눗셈 단계에서 스택 최상단 값의 부호를 확인하는 이유는, 파이썬의 나눗셈이 0을 향한 절삭(truncation toward zero)이 아니라 음의 무한대 방향으로 내림(floor)하기 때문입니다. 예를 들어 "-3/2"는 일반적인 계산기 규칙상 -1이 되어야 하지만, 파이썬에서는 -2가 됩니다. 따라서 절댓값으로 나눈 뒤 부호를 다시 붙여주는 방식으로 이를 보정합니다.
예제 코드
class Solution(object):
def calculate(self, s):
"""
:type s: str
:rtype: int
"""
stack = []
i = 0
x = ""
# 공백 제거
for j in s:
if j != " ":
x += j
s = x
n = len(s)
while i < n:
if s[i] == '/':
i += 1
num, i = self.make_num(s, i)
if stack[-1] < 0:
stack[-1] = -1 * (abs(stack[-1]) / num)
else:
stack[-1] = stack[-1] / num
elif s[i] == '*':
i += 1
num, i = self.make_num(s, i)
stack[-1] = stack[-1] * num
elif s[i] == '-':
i += 1
num, i = self.make_num(s, i)
stack.append(-num)
elif s[i] == '+':
i += 1
num, i = self.make_num(s, i)
stack.append(num)
else:
num, i = self.make_num(s, i)
stack.append(num)
i += 1
return sum(stack)
def make_num(self, s, i):
start = i
while i < len(s) and s[i] != '/' and s[i] != '*' and s[i] != '-' and s[i] != '+':
i += 1
return int(s[start:i]), i - 1
실행 결과
입력
"3+2*2"
출력
7
복잡도 분석
시간 복잡도는 O(n), 공간 복잡도 역시 O(n)입니다. 여기서 n은 입력 문자열의 길이를 의미합니다. 문자열을 한 번만 순회하면서 연산을 처리하므로 매우 효율적인 풀이입니다.