Home BOJ - 4949 - 균형잡힌 세상
Post
Cancel

BOJ - 4949 - 균형잡힌 세상

BOJ - 4949 - 균형잡힌 세상

문제


4949번: 균형잡힌 세상

https://user-images.githubusercontent.com/71277820/162746442-1a944626-ec4a-47ca-a68a-172f4154ff95.png

문제 개념


  • 모든 왼쪽 소괄호(“(“)는 오른쪽 소괄호(“)”)와만 짝을 이뤄야 한다.
  • 모든 왼쪽 대괄호(“[“)는 오른쪽 대괄호(“]”)와만 짝을 이뤄야 한다.
  • 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
  • 모든 괄호들의 짝은 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를 판단한다.

짤막한 회고


스스로 푼 코드가 아니라.. 마음이 아프다..

한 문제를 가지고 끝까지 물고 늘어지는게 맞을까..

일정시간을 정해두고 서칭을 하며 푸는게 맞을까…(이번문제는 서칭해서 품 !)

Reference & 다른 PS 모음집


https://github.com/ggh-png/PS

[C/C++] 백준 4949번 균형잡힌 세상(Stack)

This post is licensed under CC BY 4.0 by the author.