Funcia
Lv.2parsingstackstring

괄호가 있는 계산식

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

계산기 앱에 새로 넣을 기능을 만들고 있습니다. 문자열 expression으로 수식이 주어지면 그 값을 계산해야 합니다. 수식은 다음으로만 이루어져 있습니다.

  • 00 이상 10910^9 이하의 정수 (앞에 불필요한 0이 붙지 않습니다)
  • 이항 연산자 +, -, *
  • 괄호 (, )

계산 규칙은 평소와 같습니다. 괄호 안을 먼저 계산하고, *는 +, -보다 먼저 계산하며, 우선순위가 같으면 왼쪽부터 계산합니다. 부호를 나타내는 단항 -는 없고, 공백도 없으며, 수식은 항상 올바른 형태입니다.

계산 결과가 매우 커지거나 음수가 될 수 있으므로, 결과를 1,000,000,0071{,}000{,}000{,}007로 나눈 나머지를 00 이상 1,000,000,0061{,}000{,}000{,}006 이하의 값으로 반환하세요.

입출력 예

expressionresult
"2+3*4"14
"(1-5)*(2+1)"999999995
"((1000000000*1000000000))"49

입출력 예 설명

예 1 — 곱셈을 먼저 하면 2 + 12 = 14입니다.

예 2 — (-4) × 3 = -12이고, −12-12를 1,000,000,0071{,}000{,}000{,}007로 나눈 나머지는 999,999,995999{,}999{,}995입니다.

예 3 — 101810^{18}을 1,000,000,0071{,}000{,}000{,}007로 나눈 나머지는 4949입니다. 괄호가 여러 겹이어도 값은 같습니다.

효율성

이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.

함수 시그니처

solution(expression: string) → int

제한 사항

  • 1≤1 \le expression.length ≤200,000\le 200{,}000
  • expression은 숫자, +, -, *, (, )로만 이루어진 올바른 수식입니다.
  • 수식에 나오는 각 정수는 00 이상 10910^9 이하입니다.
  • 괄호는 최대 100,000100{,}000겹까지 중첩될 수 있습니다.

기대 복잡도

시간
O(N)
공간
O(N)

입출력 예

expression기대 출력
"2+3*4"14
"(1-5)*(2+1)"999999995
"((1000000000*1000000000))"49

힌트

힌트

가장 안쪽 괄호를 찾아 계산한 뒤 문자열을 고쳐 쓰는 방식은 괄호가 깊을수록 문자열 전체를 여러 번 훑게 되어 O(N2)O(N^2)입니다.

스택 두 개(숫자 스택, 연산자 스택)로 왼쪽부터 한 번만 읽으며 계산할 수 있습니다.

  • 숫자를 읽으면 숫자 스택에 넣습니다.
  • (는 연산자 스택에 넣습니다.
  • )를 만나면 (가 나올 때까지 연산자를 꺼내 계산합니다.
  • 연산자를 만나면, 스택 맨 위 연산자의 우선순위가 같거나 높은 동안 먼저 계산한 뒤 넣습니다(왼쪽부터 계산하기 위해).

덧셈, 뺄셈, 곱셈은 모두 나머지 연산과 잘 맞으므로 매 계산마다 나머지를 취하면 됩니다. 뺄셈 뒤에는 음수가 되지 않도록 1,000,000,0071{,}000{,}000{,}007을 더해 주세요.

괄호가 10만 겹까지 중첩되므로 재귀로 구현하면 언어에 따라 호출 깊이 제한에 걸릴 수 있습니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)200 ms추정
C++ (GCC, gnu++23)200 ms도출됨
Python 3.131000 ms도출됨
Java 251000 ms도출됨
Kotlin 2.4 (JVM)1400 ms추정
C# 14 (.NET 10)1400 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample03입력·출력 공개
correctness4013판정만
performance604판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.