[Gold V] 괄호의 값 - 2504
성능 요약
메모리: 11556 KB, 시간: 76 ms
분류
자료 구조, 구현, 스택
제출 일자
2024년 1월 14일 16:01:15
문제 설명
4개의 기호 ‘(
’, ‘)
’, ‘[
’, ‘]
’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다.
- 한 쌍의 괄호로만 이루어진 ‘
()
’와 ‘[]
’는 올바른 괄호열이다. - 만일
X
가 올바른 괄호열이면 ‘(X)
’이나 ‘[X]
’도 모두 올바른 괄호열이 된다. X
와Y
모두 올바른 괄호열이라면 이들을 결합한XY
도 올바른 괄호열이 된다.
예를 들어 ‘(()[[]])
’나 ‘(())[][]
’ 는 올바른 괄호열이지만 ‘([)]
’ 나 ‘(()()[]
’ 은 모두 올바른 괄호열이 아니다. 우리는 어떤 올바른 괄호열 X
에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 값(X
)로 표시한다.
- ‘
()
’ 인 괄호열의 값은 2이다. - ‘
[]
’ 인 괄호열의 값은 3이다. - ‘
(X)
’ 의 괄호값은 2×값(X
) 으로 계산된다. - ‘
[X]
’ 의 괄호값은 3×값(X
) 으로 계산된다. - 올바른 괄호열
X
와Y
가 결합된XY
의 괄호값은 값(XY
)= 값(X
)+값(Y
) 로 계산된다.
예를 들어 ‘(()[[]])([])
’ 의 괄호값을 구해보자. ‘()[[]]
’ 의 괄호값이 2 + 3×3=11 이므로 ‘(()[[]])
’의 괄호값은 2×11=22 이다. 그리고 ‘([])
’의 값은 2×3=6 이므로 전체 괄호열의 값은 22 + 6 = 28 이다.
여러분이 풀어야 할 문제는 주어진 괄호열을 읽고 그 괄호값을 앞에서 정의한대로 계산하여 출력하는 것이다.
입력
첫째 줄에 괄호열을 나타내는 문자열(스트링)이 주어진다. 단 그 길이는 1 이상, 30 이하이다.
출력
첫째 줄에 그 괄호열의 값을 나타내는 정수를 출력한다. 만일 입력이 올바르지 못한 괄호열이면 반드시 0을 출력해야 한다.
접근 방식
1. 닫는 괄호일 때 곱해야하는지 더해야하는지 구분해주는 것이 중요하다.
2. 만약 닫는 괄호일 때 연산이 남아있다면 곱해주어야하고 만약 연산이 남아있지않다면 더해줘야한다.
3. 여는 괄호를 스택에 넣어줄 때 숫자 스택에 1을 함께 넣어주면 구별이 가능하다.(숫자 2,3만 나오고 1이 나오는 경우는 존재하지 않기 때문에 곱하거나 더하는 경우를 구분해줄 수 있음
즉, 닫는 괄호일 때 1이 나올 때 까지 곱해주고 1이면 종료한다. 그 후 스택에 넣어야 할 때 top값이 1이라면 그냥 넣고 1이 아니라면 더 해줘야한다.
import java.io.*;
import java.util.*;
class Main {
public static void main(String args[]) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String text = br.readLine();
Stack<Character> stack = new Stack<>();
Stack<Integer> result = new Stack<>();
int tmp;
for (char c : text.toCharArray()) {
// 여는 괄호일 경우 괄호 스택에 괄호를 넣고 result 스택에 1을 넣어준다.
if (c == '(' || c == '[') {
stack.push(c);
result.push(1);
}
// 닫는 괄호일 경우
else {
// 닫는 괄호인데 스택이 비어있다면 잘못된 입력값
if (stack.isEmpty()) {
result.clear();
break;
}
// 닫는 괄호별로 매칭이 되는지 확인 후 아니라면 잘못된 것이기 때문에 result를 비워주고 break;
if(c == ']'){
if(!stack.isEmpty() && stack.peek() != '['){
result.clear();
break;
}
tmp = 3;
}else {
if (!stack.isEmpty() && stack.peek() != '(') {
result.clear();
break;
}
tmp = 2;
}
// 괄호 스택에서 빼준다.
stack.pop();
// 1을 만날 때 까지 연산을 진행해준다.
while (!result.isEmpty()) {
int value = result.pop();
// 방금 빼낸 숫자가 1이라면 곱하는 연산은 그만한다.
if (value == 1) {
// 다음 숫자도 1이라면 곱하는 연산을 준비해야하고 1이 아니라면 더해줘야한다.(괄호가 없기 때문에)
if(!result.isEmpty() && result.peek() != 1){
tmp += result.pop();
}
result.push(tmp);
break;
}
// 1이 아니라면 곱해준다.
tmp *= value;
}
}
}
// 연산이 남아있거나 result이 비어있다면 잘못된 연산이다.
System.out.println(!stack.isEmpty() || result.isEmpty()? 0 : result.pop());
}
}
'알고리즘 - Baekjoon > Gold' 카테고리의 다른 글
[백준] 11404번 : 플로이드 Gold4(골드4) - JAVA[자바] (0) | 2024.01.17 |
---|---|
[백준] 1068번 : 트리 Gold5(골드5) - JAVA[자바] (1) | 2024.01.16 |
[백준] 1987번 : 알파벳 Gold4(골드4) - JAVA[자바] (2) | 2024.01.14 |
[백준] 14500번 : 테트로미노 Gold4(골드4) - JAVA[자바] (0) | 2024.01.12 |
[백준] 1753번 : 최단경로 Gold4(골드4) - JAVA[자바] (0) | 2024.01.11 |