Lv.2parsingstackstring
괄호가 있는 계산식
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
계산기 앱에 새로 넣을 기능을 만들고 있습니다. 문자열 expression으로 수식이 주어지면 그 값을 계산해야 합니다.
수식은 다음으로만 이루어져 있습니다.
- 이상 이하의 정수 (앞에 불필요한
0이 붙지 않습니다) - 이항 연산자
+,-,* - 괄호
(,)
계산 규칙은 평소와 같습니다. 괄호 안을 먼저 계산하고, *는 +, -보다 먼저 계산하며, 우선순위가 같으면 왼쪽부터 계산합니다.
부호를 나타내는 단항 -는 없고, 공백도 없으며, 수식은 항상 올바른 형태입니다.
계산 결과가 매우 커지거나 음수가 될 수 있으므로, 결과를 로 나눈 나머지를 이상 이하의 값으로 반환하세요.
입출력 예
| expression | result |
|---|---|
"2+3*4" | 14 |
"(1-5)*(2+1)" | 999999995 |
"((1000000000*1000000000))" | 49 |
입출력 예 설명
예 1 — 곱셈을 먼저 하면 2 + 12 = 14입니다.
예 2 — (-4) × 3 = -12이고, 를 로 나눈 나머지는 입니다.
예 3 — 을 로 나눈 나머지는 입니다. 괄호가 여러 겹이어도 값은 같습니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(expression: string) → int
제한 사항
-
expression.length expression은 숫자,+,-,*,(,)로만 이루어진 올바른 수식입니다.- 수식에 나오는 각 정수는 이상 이하입니다.
- 괄호는 최대 겹까지 중첩될 수 있습니다.
기대 복잡도
- 시간
- O(N)
- 공간
- O(N)
입출력 예
| expression | 기대 출력 |
|---|---|
"2+3*4" | 14 |
"(1-5)*(2+1)" | 999999995 |
"((1000000000*1000000000))" | 49 |
힌트
힌트
가장 안쪽 괄호를 찾아 계산한 뒤 문자열을 고쳐 쓰는 방식은 괄호가 깊을수록 문자열 전체를 여러 번 훑게 되어 입니다.
스택 두 개(숫자 스택, 연산자 스택)로 왼쪽부터 한 번만 읽으며 계산할 수 있습니다.
- 숫자를 읽으면 숫자 스택에 넣습니다.
(는 연산자 스택에 넣습니다.)를 만나면(가 나올 때까지 연산자를 꺼내 계산합니다.- 연산자를 만나면, 스택 맨 위 연산자의 우선순위가 같거나 높은 동안 먼저 계산한 뒤 넣습니다(왼쪽부터 계산하기 위해).
덧셈, 뺄셈, 곱셈은 모두 나머지 연산과 잘 맞으므로 매 계산마다 나머지를 취하면 됩니다. 뺄셈 뒤에는 음수가 되지 않도록 을 더해 주세요.
괄호가 10만 겹까지 중첩되므로 재귀로 구현하면 언어에 따라 호출 깊이 제한에 걸릴 수 있습니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | 추정 |
| C++ (GCC, gnu++23) | 200 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 1000 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1400 ms | 추정 |
| C# 14 (.NET 10) | 1400 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 13 | 판정만 |
| performance | 60 | 4 | 판정만 |