[BOJ] 2504. 괄호의 값
15 Apr 2026
Reading time ~8 minutes
내 풀이
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.next();
Stack<Character> stack = new Stack(); // 괄호 올바른지 체크.
// 괄호가 짝이 맞는지 검사. 짝이 맞다면 stack에서 pop이 되므로 스택이 완전히 비어있게 된다.
for(int i = 0; i < s.length(); i++) {
if(!stack.isEmpty() && stack.peek() == '(' && s.charAt(i) == ')') stack.pop(); // 짝이 맞으면 열린 괄호 '('를 스택에서 꺼낸다.
else if(!stack.isEmpty() && stack.peek() == '[' && s.charAt(i) == ']') stack.pop(); // 짝이 맞으면 열린 괄호 '['를 스택에서 꺼낸다.
else stack.push(s.charAt(i)); // 짝이 안맞으면 stack에 저장한다.
}
// 짝이 맞지 않으면 스택에 무언가가 남아있게 되므로 정답을 0으로 출력하고 프로그램을 종료할 수 있도록 main 함수를 return 한다.
if(!stack.isEmpty()) {
System.out.println("0");
return;
}
// 열린 문자를 담기 위한 스택, 이 때 Pare 클래스를 이용해서 괄호의 인덱스도 함께 담아준다.
Stack<Pare> stack1 = new Stack<>();
// 괄호가 부분적으로 닫힌 부분 까지의 값들을 계산하여 저장하는 스택. 이 때 PartSum 클래스를 이용해서 시작과 끝의 인덱스도 함께 담아준다.
Stack<PartSum> stack2 = new Stack<>();
// 괄호가 완전히 닫힌 부분 까지의 값들을 계산하여 저장하는 스택.
Stack<Integer> stack3 = new Stack<>();
// 첫 괄호는 인덱스를 0으로 해서 stack1에 넣는다.
stack1.push(new Pare(s.charAt(0),0));
// 두 번째 괄호부터 마지막 괄호까지 탐색.
for(int i = 1; i < s.length(); i++) {
// 스택에 1개의 '(' 괄호가 남아 있으면서 현재 검사하는 인덱스에 위치한 괄호가 ')'일 때
// 그리고 그 두 괄호 사이에 어떤 괄호도 존재하지 않을 때 <= '('는 i-1번 인덱스에 ')'는 i번 인덱스에 있을 때
if(stack1.size() == 1 && stack1.peek().bracket == '(' && s.charAt(i) == ')' && stack1.peek().index == i - 1) {
stack3.push(2); // 스택에 1개의 괄호만 남아있으므로 완전히 닫힌 경우이므로 stack3에 그리고 '(', ')'가 연달아 존재하므로 값 2를 저장한다.
stack1.pop(); // 그리고 stack1에 저장된 열린 괄호 '(' 하나를 처리하였으므로 pop하여 삭제한다.
}
// 스택에 1개의 '[' 괄호가 남아 있으면서 현재 검사하는 인덱스에 위치한 괄호가 ']'일 때
// 그리고 그 두 괄호 사이에 어떤 괄호도 존재하지 않을 때 <= '['는 i-1번 인덱스에 ']'는 i번 인덱스에 있을 때
else if(stack1.size() == 1 && stack1.peek().bracket == '[' && s.charAt(i) == ']' && stack1.peek().index == i - 1) {
stack3.push(3); // 스택에 1개의 괄호만 남아있으므로 완전히 닫힌 경우이므로 stack3에 그리고 '[', ']'가 연달아 존재하므로 값 3를 저장한다.
stack1.pop(); // 그리고 stack1에 저장된 열린 괄호 '[' 하나를 처리하였으므로 pop하여 삭제한다.
}
// 스택에 1개의 '(' 괄호가 남아 있으면서 현재 검사하는 인덱스에 위치한 괄호가 ')'일 때
// 그리고 그 두 괄호 사이에 어떤 괄호가 존재할 때(존재하지 않았다면 위에서 이미 처리되기 때문)
// => 괄호가 '(', ')' 로 완전히 닫혔으므로 현재 인덱스까지 부분합들을 더한 후 2를 곱해서
// 괄호가 완전히 닫힌 부분까지의 값들을 계산하여 stack3에 저장.
else if(stack1.size() == 1 && stack1.peek().bracket == '(' && s.charAt(i) == ')') {
int sum = 0; // 계산할 구간내에서의 부분합들의 합을 구하기 위한 변수로 덧셈의 항등원인 0으로 초기화.
int limit_index = stack1.peek().index; // 계산할 구간 범위의 왼쪽 부분의 한계값 설정.
// stack2에서 계산한 부분합들 중에서 계산할 구간 범위의 왼쪽 부분보다 앞에 있다면 무시해야하므로
while(!stack2.isEmpty() && stack2.peek().end_index > limit_index) {
// stack2에서 계산한 부분합들 중에서 계산할 구간 범위의 왼쪽 부분보다 뒤에 있다면
sum += stack2.pop().value; // stack2에서 꺼내서 저장했었던 부분합 값을 하나씩 더한다.
}
stack3.push(sum*2); // 괄호가 완전히 닫힌 부분이므로 값을 stack3에 저장한다.
stack1.pop(); // 그리고 stack1에 저장된 열린 괄호 '(' 하나를 처리하였으므로 pop하여 삭제한다.
}
// 스택에 1개의 '[' 괄호가 남아 있으면서 현재 검사하는 인덱스에 위치한 괄호가 ']'일 때
// 그리고 그 두 괄호 사이에 어떤 괄호가 존재할 때(존재하지 않았다면 위에서 이미 처리되기 때문)
// => 괄호가 '[', ']' 로 완전히 닫혔으므로 현재 인덱스까지 부분합들을 더한 후 3을 곱해서
// 괄호가 완전히 닫힌 해당 구간까지의 값들을 계산하여 stack3에 저장한다.
else if(stack1.size() == 1 && stack1.peek().bracket == '[' && s.charAt(i) == ']') {
int sum = 0; // 계산할 구간내에서의 부분합들의 합을 구하기 위한 변수로 덧셈의 항등원인 0으로 초기화.
int limit_index = stack1.peek().index; // 계산할 구간 범위의 왼쪽 부분의 한계값 설정.
// stack2에서 계산한 부분합들 중에서 계산할 구간 범위의 왼쪽 부분보다 앞에 있다면 무시해야하므로
while(!stack2.isEmpty() && stack2.peek().end_index > limit_index) {
// stack2에서 계산한 부분합들 중에서 계산할 구간 범위의 왼쪽 부분보다 뒤에 있다면
sum += stack2.pop().value; // stack2에서 꺼내서 저장했었던 부분합 값을 하나씩 더한다.
}
stack3.push(sum*3); // 괄호가 완전히 닫힌 부분이므로 값을 stack3에 저장한다.
stack1.pop(); // 그리고 stack1에 저장된 열린 괄호 '(' 하나를 처리하였으므로 pop하여 삭제한다.
}
// 스택에 1개 이상의 괄호가 있으므로 짝이 맞다하더라도 괄호가 완전 닫히지 않았기 때문에 부분합을 구한다. 그리고 시작, 끝 인덱스와 함께 저장한다.
// '('과 ')'가 연달아 있으므로 부분합으로는 2를 그리고 시작 인덱스에는 시작 괄호의 인덱스인 i-1을, 끝 인덱스에는 끝 괄호의 인덱스인 i를 저장한다.
else if(stack1.size() > 1 && stack1.peek().bracket == '(' && s.charAt(i) == ')' && stack1.peek().index == i - 1) {
stack2.push(new PartSum(2,i-1,i)); // 부분합을 stack2에 저장한다.
stack1.pop(); // 그리고 stack1에 저장된 열린 괄호 '(' 하나를 처리하였으므로 pop하여 삭제한다.
}
// 스택에 1개 이상의 괄호가 있으므로 짝이 맞다하더라도 괄호가 완전 닫히지 않았기 때문에 부분 합을 구한다. 그리고 시작, 끝 인덱스와 함께 저장한다.
// '['과 ']'가 연달아 있으므로 부분 합으로는 3을 그리고 시작 인덱스에는 시작 괄호의 인덱스인 i-1을, 끝 인덱스에는 끝 괄호의 인덱스인 i를 저장한다.
// 부분합을 저장하기 위한 것이므로 stack2에 저장한다.
else if(stack1.size() > 1 && stack1.peek().bracket == '[' && s.charAt(i) == ']' && stack1.peek().index == i - 1) {
stack2.push(new PartSum(3,i-1,i)); // 부분합을 stack2에 저장한다.
stack1.pop(); // 그리고 stack1에 저장된 열린 괄호 '(' 하나를 처리하였으므로 pop하여 삭제한다.
}
// 스택에 1개 이상의 괄호가 있으므로 짝이 맞다하더라도 괄호가 완전 닫히지 않았기 때문에 부분합을 구한다. 그리고 시작, 끝 인덱스와 함께 저장한다.
// '('과 ')'가 연달아 있지 않으므로 구간 내에 있는 부분합들을 모두 더한 후 2배를 해준다.
// 그리고 새로운 구간의 시작 인덱스에는 구간 내의 부분합들 가운데 가장 작은 시작 인덱스 값에서 -1을, 끝 인덱스에는 가장 큰 끝 인덱스 값에서 +1을 해서 새로운 구간까지의 부분합을 만든다.
// 이 새로운 구간의 부분합을 stack2에 저장한다.
else if(stack1.size() > 1 && stack1.peek().bracket == '(' && s.charAt(i) == ')' && stack1.peek().index != i - 1) {
int sum = 0; // 계산할 구간내에서의 부분합들의 합을 구하기 위한 변수로 덧셈의 항등원인 0으로 초기화.
int start_index = s.length(); // 최소값을 구해야 하므로 우선 될 수 있는 가장 최대값으로 초기화.
int end_index = 0; // 최대값을 구해야 하므로 우선 될 수 있는 가장 최소값으로 초기화.
int limit_index = stack1.peek().index; // 계산할 구간 범위의 왼쪽 부분의 한계값 설정.
// stack2에서 계산한 부분합들 중에서 계산할 구간 범위의 왼쪽 부분보다 앞에 있다면 무시해야하므로
while(!stack2.isEmpty() && stack2.peek().end_index > limit_index) {
// stack2에서 계산한 부분합들 중에서 계산할 구간 범위의 왼쪽 부분보다 뒤에 있다면
PartSum ps = stack2.pop();
sum += ps.value; // stack2에서 꺼내서 저장했었던 부분합 값을 하나씩 더한다.
start_index = Math.min(ps.start_index,start_index); // 새로운 구간의 시작 인덱스는 계산할 구간 범위 내에 있는 stack2에서 꺼낸 값 중 가장 작은 값으로 설정한다.
end_index = Math.max(ps.end_index,end_index); // 새로운 구간의 끝 인덱스는 계산할 구간 범위 내에 있는 stack2에서 꺼낸 값 중 가장 큰 값으로 설정한다.
}
stack2.push(new PartSum(sum*2, start_index - 1, end_index + 1)); // 시작 인덱스는 가장 작은 값보다 1 작은 값으로, 끝 인덱스는 가장 큰 값보다 1 큰 값으로 설정한다.
// 값을 2배 하고 해당 구간까지를 새로운 부분합으로 하여 stack2에 저장한다.
stack1.pop(); // 열린 괄호 하나를 처리하였으므로 stack1에서 꺼내서 삭제해준다.
}
// 스택에 1개 이상의 괄호가 있으므로 짝이 맞다하더라도 괄호가 완전 닫히지 않았기 때문에 부분합을 구한다. 그리고 시작, 끝 인덱스와 함께 저장한다.
// '('과 ')'가 연달아 있지 않으므로 구간 내에 있는 부분합들을 모두 더한 후 2배를 해준다.
// 새로운 구간의 시작 인덱스는 구간 내의 부분합들 중에 시작 인덱스 값 중 가장 작은 값에서 -1을, 끝 인덱스는 끝 인덱스 값 중 가장 큰 값에서 +1을 해서 새로운 구간까지의 부분합을 만든다.
// 이 새로운 구간의 부분합을 stack2에 저장한다.
else if(stack1.size() > 1 && stack1.peek().bracket == '[' && s.charAt(i) == ']' && stack1.peek().index != i - 1) {
int sum = 0; // 계산할 구간내에서의 부분합들의 합을 구하기 위한 변수로 덧셈의 항등원인 0으로 초기화.
int start_index = s.length(); // 최소값을 구해야 하므로 우선 될 수 있는 가장 최대값으로 초기화.
int end_index = 0; // 최대값을 구해야 하므로 우선 될 수 있는 가장 최소값으로 초기화.
int limit_index = stack1.peek().index; // 계산할 구간 범위의 왼쪽 부분의 한계값 설정.
// stack2에서 계산한 부분합들 중에서 계산할 구간 범위의 왼쪽 부분보다 앞에 있다면 무시해야하므로
while(!stack2.isEmpty() && stack2.peek().end_index > limit_index) {
PartSum ps = stack2.pop(); // stack2에서 저장했었던 부분합 하나를 꺼낸다.
sum += ps.value; // stack2에서 꺼내서 저장했었던 부분합 값을 하나씩 더한다.
start_index = Math.min(ps.start_index,start_index); // 새로운 구간의 시작 인덱스는 계산할 구간 범위 내에 있는 stack2에서 꺼낸 값 중 가장 작은 값으로 설정한다.
end_index = Math.max(ps.end_index, end_index); // 새로운 구간의 끝 인덱스는 계산할 구간 범위 내에 있는 stack2에서 꺼낸 값 중 가장 큰 값으로 설정한다.
}
stack2.push(new PartSum(sum*3, start_index - 1, end_index + 1)); // 시작 인덱스는 가장 작은 값보다 1 작은 값으로, 끝 인덱스는 가장 큰 값보다 1 큰 값으로 설정한다.
// 값을 3배 하고 해당 구간까지를 새로운 부분합으로 하여 stack2에 저장한다.
stack1.pop(); // 열린 괄호 하나를 처리하였으므로 stack1에서 꺼내서 삭제해준다.
}
// 짝이 맞지 않는 경우
else {
stack1.push(new Pare(s.charAt(i),i)); // stack1에 괄호를 인덱스와 함께 저장한다.
}
}
int sum = 0; // 괄호가 완전히 닫힌 구간들의 값들의 합을 구하기 위한 변수로 덧셈의 항등원인 0으로 초기화.
while(!stack3.isEmpty()) {
sum += stack3.pop(); // 괄호가 완전히 닫힌 구간들의 값들을 전부 더해준다.
}
System.out.println(sum); // 괄호가 완전히 닫힌 구간들의 값들의 합을 출력한다.
}
// 괄호 및 괄호 위치를 담을 클래스
private static class Pare {
char bracket;
int index;
Pare(char bracket, int index) {
this.bracket = bracket;
this.index = index;
}
@Override
public String toString() {
return "(" + bracket + ", " + index + ")";
}
}
// 구간의 시작위치와 끝 위치 그리고 start_index부터 end_index까지 구간의 계산값을 담을 클래스.
private static class PartSum {
int value, start_index, end_index;
PartSum(int value, int start_index, int end_index) {
this.value = value;
this.start_index = start_index;
this.end_index = end_index;
}
@Override
public String toString() {
return "(" + value + ", " + start_index + ", " + end_index + ")";
}
}
}