BOJ - 4949 - 균형잡힌 세상
문제
문제 개념
- 모든 왼쪽 소괄호(“(“)는 오른쪽 소괄호(“)”)와만 짝을 이뤄야 한다.
- 모든 왼쪽 대괄호(“[“)는 오른쪽 대괄호(“]”)와만 짝을 이뤄야 한다.
- 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
- 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
- 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.
즉. 올바른 VPS 괄호 여닫이여야만 한다.
구현
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
53
54
55
56
#include <iostream>
#include <vector>
using namespace std;
// 입력 : 공백이 있는 문자열 ... 오로지 '.'만이 문자열의 끝을 알림.
// (), []만이 존재함.
// ( or [ 둘이 ([)] 인 경우 어떻게 처리할까..?
// ()[ || ([) 를 어캐 구분할까
int main()
{
vector<string> answer; // output
string str;
answer.clear();
while (1)
{
// 문자열 입력
getline(cin, str);
// stack init
vector<char> VectorStack;
if(str[0] == '.') break;
// 판별 ()
for(int i=0; i < str.size(); i++)
{ // 괄호를 입력 받으면
// 시작 괄호면 스택쌓기
if(str[i] == '(') VectorStack.push_back('(');
if(str[i] == '[') VectorStack.push_back('[');
if(str[i] == ')')
{ // 스택이 비어있지 않고 스택의 최 상단에 시작괄호가 있다면 스택제거
// () 인 경우 : 빈 스택으로 만듬
if(!VectorStack.empty() && *(VectorStack.end()-1) == '(')
VectorStack.pop_back();
// 빈 스택에 닫는괄호가 들어오면 no
// ) 인 경우 : no
else{ answer.push_back("no"); break; }
}
if(str[i] == ']')
{ // 스택이 비어있지 않고 스택의 최 상단에 시작괄호가 있다면 스택제거
// [] 인 경우 : 빈 스택으로 만듬
if(!VectorStack.empty() && *(VectorStack.end()-1) == '[')
VectorStack.pop_back();
// 빈 스택에 닫는괄호가 들어오면 no
// ) 인 경우 : no
else{ answer.push_back("no"); break; }
}
// 스택이 비어있고 .이 나오기 전까지 입력된 문자열을 확인했을 경우
if (VectorStack.empty() && i == str.length() - 2)
answer.push_back("yes");
// 스택이 비어있지 않고 입력된 문자열을 확인했을 경우
else if (!VectorStack.empty() && i == str.length() - 2)
answer.push_back("no");
}
}
for(auto el : answer)
cout << el << '\n';
}
SOL
- 스택 구조의 조건을 만들어 VPS를 판단한다.
짤막한 회고
스스로 푼 코드가 아니라.. 마음이 아프다..
한 문제를 가지고 끝까지 물고 늘어지는게 맞을까..
일정시간을 정해두고 서칭을 하며 푸는게 맞을까…(이번문제는 서칭해서 품 !)