SW Expert Academy 의 1218번 - 괄호 짝짓기 문제입니다.
이번 문제가 들어있는 파트가 Stack 자료구조에 대한 강의였어서 그런지, 스택을 활용하라는 문제가 나온 것 같습니다.
괄호문자 4종류 ‘(),[],{},<>’ 가 무작위하게 인풋에서 배열되어 주어집니다.
이 문자열에 사용된 괄호들이 짝이 올바르게 맞는지를 판별하는 문제입니다.
- 난이도 : 2~3
문제 조건
- 총 10개의 테스트 케이스가 주어진다.
Input
첫 줄에는 테스트 케이스 번호, 그 다음 줄에는 문자열이 주어진다.
Output
짝이 올바르게 맞아서 유효하면 1, 유효하지 않으면 0을 출력한다.
처음에 생각한 아이디어
stack 자료구조를 설명하는 강의에서, 괄호의 짝이 맞는지 아닌지를 판별하는 데 스택이 쓰인다고 설명이 나온 적이 있습니다.
그 때의 개념 설명을 참고해서 코딩을 하면 될 것 같습니다.
- 왼쪽 괄호를 만나면 스택에 push 하고, 오른쪽 괄호를 만나면 스택에 있는 문자를 pop 한 뒤 비교해서 짝이 맞으면 넘어갑니다. 짝이 맞지 않으면 유효하지 않습니다.
- 마지막까지 조사했는데 스택에 왼쪽 괄호가 남아있다면, 맞는 짝이 없었다는 이야기므로 유효하지 않습니다.
- 만난 오른쪽 괄호와 비교할 왼쪽 괄호를 스택에서 pop 해야 하는데, 스택이 비어 있으면 유효하지 않습니다.
소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <stack>
using namespace std;
int main() {
int len, flag = 0;
char c[1000], pStr, str;
stack<char> s;
for (int T = 1; T <= 10; T++) {
cin >> len;
cin.get(str);
cin.getline(c, len+1);
for (int i = 0; i < len; i++) {
if (c[i] == '(' || c[i] == '[' || c[i] == '{' || c[i] == '<') {
// 왼쪽 괄호이면
s.push(c[i]);
}
else { // 오른쪽 괄호를 만나면
if (!s.empty()) { // 스택이 비어있지 않을 때,
pStr = s.top(); // 맨 위의 문자를 저장 후
s.pop(); // 스택에서 pop 한다.
if ((pStr == '(' && c[i] == ')') || ((pStr == '[' && c[i] == ']'))
|| ((pStr == '{' && c[i] == '}')) || ((pStr == '<' && c[i] == '>'))) {
flag = 1;
}
else { // 유효하지 않음
flag = 0;
break;
}
}
else // 스택이 비어있으면 빠져나온다.
{
flag = 0;
break;
}
}
}
// 문자열 길이만큼 다 보았을 때, 스택이 비어 있지 않다면?
if (!s.empty())
flag = 0;
cout << "#" << T << " " << flag << endl;
while (!s.empty()) {
s.pop();
}
}
}
c++의 STL에서 제공하는 stack 자료구조를 사용하였습니다.