https://www.acmicpc.net/problem/2504
문제
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
(()[[]])([])
예제 출력1
28
예제 입력2
[][]((])
예제 출력2
0
풀이 1
수식의 괄호 쌍 활용 문제다. 문제가 좀 복잡해서 정리해 봤다.
여는 괄호이면 -> stack1에 push
올바른 괄호이면 -> 올바른 여는 괄호 이전 괄호가 여는 괄호이면 -> 그 괄호의 값(2 또는 3)을 stack2에 push
올바른 괄호이면 -> 올바른 여는 괄호 이전 괄호가 여는 괄호가 아니면 -> 결과값에 해당 괄호의 값(2 또는 3)을 합산
올바른 괄호 처리 후 또 올바른 괄호이면 -> 이전 값(이전 올바른 괄호 값) * stack2.Pop()을 결과값에 합산
코드 1 (오답)
namespace 스택
{
internal class BOJ2504_괄호의_값
{
static void Main(string[] args)
{
StreamReader sr = new StreamReader(Console.OpenStandardInput());
StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
Stack<char> stack1 = new Stack<char>();
Stack<int> stack2 = new Stack<int>();
bool isCorrect = false;
int preNum = 0;
int result = 0;
string input = sr.ReadLine();
for(int i = 0; i < input.Length; i++)
{
if (input[i] == '(' || input[i] == '[')
{
stack1.Push(input[i]);
}
else
{
// 올바른 괄호이면
if (stack1.Peek() == '(' && input[i] == ')')
{
char pre = stack1.Pop();
if (isCorrect)
{
result += preNum * stack2.Pop();
preNum = 1;
isCorrect = false;
continue;
}
if (stack1.Peek() == '(' || stack1.Peek() == '[')
{
if (stack1.Peek() == '(')
{
stack2.Push(2);
if (input[i+1] != ')' || input[i+1] != ']')
{
if(pre == '(')
{
preNum = 2;
result += preNum;
}
else if(pre == '[')
{
preNum = 3;
result += preNum;
}
}
}
else if (stack1.Peek() == '[')
{
stack2.Push(3);
}
}
else
{
if (pre == '(')
{
preNum = 2;
result += preNum;
}
else if (pre == '[')
{
preNum = 3;
result += preNum;
}
}
isCorrect = true;
}
else if(stack1.Peek() == '[' && input[i] == ']')
{
char pre = stack1.Pop();
if (isCorrect)
{
result += preNum * stack2.Pop();
preNum = 1;
isCorrect = false;
continue;
}
if (stack1.Peek() == '(' || stack1.Peek() == '[')
{
if (stack1.Peek() == '(')
{
stack2.Push(2);
if (input[i + 1] != ')' || input[i + 1] != ']')
{
if (pre == '(')
{
preNum = 2;
result += preNum;
}
else if (pre == '[')
{
preNum = 3;
result += preNum;
}
}
}
else if (stack1.Peek() == '[')
{
stack2.Push(3);
}
}
else
{
if (pre == '(')
{
preNum = 2;
result += preNum;
}
else if (pre == '[')
{
preNum = 3;
result += preNum;
}
}
isCorrect = true;
}
}
}
sw.WriteLine(result);
sw.Close();
sr.Close();
}
}
}
예제를 통과하지 못해 오답처리가 되었다. 내일 다시 한번 풀어봐야겠다.
풀이 2
올바른 괄호다 -> stack2.push(괄호값)
올바른 괄호 다음이 여는 괄호다 -> stack2.pop()을 결과값에 합산
올바른 괄호 다음이 닫는 괄호다 혹은 올바른 괄호 다음이 없다
-> 그렇다 -> 해당 괄호 값 * stack2.pop()을 stack2에 push ( stack2.push(stack2.pop()) )
-> 그렇지 않다 -> 결과값 += stack2.pop()
코드 2 (오답)
namespace 스택
{
internal class BOJ2504_괄호의_값
{
static void Main(string[] args)
{
StreamReader sr = new StreamReader(Console.OpenStandardInput());
StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
Stack<char> stack1 = new Stack<char>();
Stack<int> stack2 = new Stack<int>();
int result = 0;
string input = "";
input = sr.ReadLine();
for(int i = 0; i < input.Length; i++)
{
if (input[i] == '(' || input[i] == '[')
{
stack1.Push(input[i]);
}
else
{
// 올바른 괄호라면
if(stack1.Peek() == '(' && input[i] == ')')
{
stack1.Pop();
stack2.Push(2);
if (i + 1 < input.Length && (input[i + 1] == '(' || input[i + 1] == '['))
{
result += stack2.Pop();
}
else if (i + 1 < input.Length && (input[i + 1] == ')' || input[i + 1] == ']') || i + 1 == input.Length - 1)
{
if (i + 1 != input.Length - 1)
{
if(stack1.Peek() == '(' && input[i+1] == ')')
{
stack2.Push(2 * stack2.Pop());
}
else if(stack1.Peek() == '[' && input[i+1] == ']')
{
stack2.Push(3 * stack2.Pop());
}
else
{
result += stack2.Pop();
}
}
else
{
result += stack2.Pop();
break;
}
}
}
else if(stack1.Peek() == '[' && input[i] == ']')
{
stack1.Pop();
stack2.Push(3);
if (i + 1 < input.Length && (input[i + 1] == '(' || input[i + 1] == '['))
{
result += stack2.Pop();
}
else if (i + 1 < input.Length && (input[i + 1] == ')' || input[i + 1] == ']') || i + 1 == input.Length - 1)
{
if (i + 1 != input.Length - 1)
{
if (stack1.Peek() == '(' && input[i + 1] == ')')
{
stack2.Push(2 * stack2.Pop());
}
else if (stack1.Peek() == '[' && input[i + 1] == ']')
{
stack2.Push(3 * stack2.Pop());
}
else
{
result += stack2.Pop();
}
}
else
{
result += stack2.Pop();
break;
}
}
}
//
}
}
sw.WriteLine(result);
sw.Close();
sr.Close();
}
}
}
이것도 오답이다. 내일은 정답 코드를 보며 이해하고, 내 코드는 왜 틀렸는지 파악 및 수정해 보겠다.
풀이 3
정답 코드를 보고 왔다. 분배법칙을 사용한 방식이었다.
(()[[]])([])을 예시로 보자.
일단 눈대중으로 풀어보면 이 괄호는 이렇게 계산된다.
2*(2+3*3) + 2*3 = 2*11 + 2*3 = 22+6 = 28
2*(2+3*3) + 2*3을 분배법칙으로 풀어보자.
2*2 + 2*3*3 + 2*3이다.
다시 예시 괄호를 보자.
(()[[]])([])
여는 괄호가 나오면 해당 괄호 값을 num에 곱연산하여 누적해 보자. 그리고 여는 괄호를 Stack에 Push 하자.
((
첫 번째와 두 번째가 여는 괄호다.
2*2를 num에 누적하자. Stack에 '('을 Push 하자.
num = 2*2
닫는 괄호가 나오면 해당 닫는 괄호가 직전 괄호와 비교했을 때 한 쌍을 만드는 괄호가 된다면 지금까지 계산된 num을 sum에 누적하자. 계산 처리가 되었으니 Stack을 Pop 해서 한 쌍 괄호 완료 처리를 해두자.
)
닫는 괄호가 나왔다. 해당 닫는 괄호는 직전 괄호와 비교해 보자. 한 쌍이 만들어진다. 지금까지 계산된 num을 sum에 누적하자.
계산 처리가 되었으니 Stack을 Pop 하자. 그리고 num을 해당 닫는 괄호 값으로 나누어 다음 계산이 잘못되지 않도록 하자.
sum = 2*2
num = 2*2/2 = 2
[[
여는 괄호가 나왔으니 해당 괄호 값을 num에 곱연산하여 누적하자. 그리고 Stack에 '['을 Push 하자.
num = 2*3*3
]]
닫는 괄호가 나왔다. 첫 번째 ]는 직전 괄호와 비교해 보니 한 쌍이 만들어진다. 지금까지 계산된 num을 sum에 누적하자.
num을 해당 닫는 괄호 값으로 나누자.
sum = 2*2 + 2*3*3
num = 2*3
두 번째 ]은 직전 괄호와 비교해 보니 한 쌍이 만들어지지 않는다. num을 해당 닫는 괄호 값으로 나누자.
num = 2
)
닫는 괄호가 나왔다. 직전 괄호와 비교해보니 한 쌍이 만들어지지 않는다. num을 해당 닫는 괄호 값으로 나누자.
num = 1
sum을 보자.
sum = 2*2 + 2*3*3이다.
좀 전에 눈대중으로 풀었던 sum을 보자. 2*2 + 2*3*3 + 2*3
이렇게 분배법칙을 Stack을 이용해서 풀 수 있다.
이어서 계산해 보자.
(
여는 괄호다. (는 2이니 2를 Stack에 Push 하자.
num을 곱연산하자.
num = 2
[
여는 괄호다. [은 3이다. 3을 Stack에 Push하자.
num을 곱연산하자.
num = 2*3
]
닫는 괄호다. 직전 괄호와 비교해 보자.
직전 괄호가 [이다. 한 쌍이 만들어진다. 지금까지 계산된 num을 sum에 누적하자. num을 해당 닫는 괄호 값으로 나누자.
sum = 2*2 + 2*3*3 + 2*3
num = 2
]
닫는 괄호다. 직전 괄호와 비교해보자.
직접 괄호는 ]이다. 한 쌍이 만들어지지 않는다. num을 해당 닫는 괄호값으로 나누자.
num = 1
괄호 문자열을 다 읽었다.
sum을 출력하자.
코드
internal class BOJ2504_괄호의_값
{
static void Main(string[] args)
{
StreamReader sr = new StreamReader(Console.OpenStandardInput());
StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
Stack<char> stack = new Stack<char>();
string str = sr.ReadLine();
int sum = 0; // 누적해서 더해질 값
int num = 1; // 곱해질 값
bool isSuccess = true;
for(int i = 0; i < str.Length; i++)
{
if (str[i] == '(')
{
num *= 2; // 소괄호가 나오면 곱해질 값 2배 증가
stack.Push(str[i]);
}
else if (str[i] == '[')
{
num *= 3; // 대괄호가 나오면 곱해질 값 3배 증가
stack.Push(str[i]);
}
else if (str[i] == ')')
{
if(stack.Count == 0 || stack.Peek() != '(')
{
isSuccess = false;
break;
}
// 직전 괄호가 여는 괄호였다면 sum에 값 추가
if (str[i-1] == '(')
{
sum += num;
}
stack.Pop();
num /= 2; // 소괄호 쌍이 사라졌으니 2로 나눔
}
else if (str[i] == ']')
{
if(stack.Count == 0 || stack.Peek() != '[')
{
isSuccess = false;
break;
}
if (str[i-1] == '[')
{
sum += num;
}
stack.Pop();
num /= 3;
}
}
if(isSuccess && stack.Count == 0)
{
sw.WriteLine(sum);
}
else
{
sw.WriteLine(0);
}
sr.Close();
sw.Close();
}
}
배운 점, 느낀 점
눈대중으로 푼 것을 코드로 정리하려니 잘 안 되었다. 끝이 난 괄호와 끝이 난 괄호 사이 값(XY) 계산을 어떻게 코드로 표현해야 할지, 그리고 그것을(XY) 묶는 괄호값을 또 곱해야 하니 이걸 어떻게 코드로 표현하는지 풀리지 않았다.
분배법칙 풀이를 보니 이게 정말 스택을 제대로 효율적으로 사용하는 방법이 아닌가 싶었다.
일반적으로는 내가 눈대중으로 푼 것을 코드로 구현하는 것 같다. 안쪽 괄호를 계산하고 바깥쪽 괄호를 계산하는 방식으로.
그런데 이 방식으로 풀면 스택을 2개를 써야 한다.
그러나 분배법칙 방식은 스택 하나만 쓰면 된다. 훨씬 가볍고 좋은 코드인 것 같다.
'자료구조, 코딩테스트 > 스택(Stack)' 카테고리의 다른 글
| [코딩테스트] BOJ 2493 - 탑 (실패) (0) | 2026.04.20 |
|---|---|
| [코딩테스트] BOJ 1874 - 스택 수열 (성공) (0) | 2026.04.16 |
| [코딩테스트] BOJ 10799 - 쇠막대기 (실패) (0) | 2026.04.12 |
| [코딩테스트] 스택(Stack) 활용 - 수식의 괄호 쌍 (0) | 2026.04.12 |
| [코딩테스트] BOJ 10773 - 제로 (성공) (0) | 2026.04.09 |