[C++] 괄호

🍟
문제 사이트: 백준
문제 난이도: Silver IV
문제 번호: 9012

 

🚩 문제

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다.

여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다.

 

입력: 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 주어진다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다. 하나의 괄호 문자열의 길이는 2 이상 50 이하이다.

 

출력: 출력은 표준 출력을 사용한다. 만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력해야 한다.

 

예제 입력:

6
(())())
(((()())()
(()())((()))
((()()(()))(((())))()
()()()()(()()())()
(()((())()(

 

예제 출력:

NO
NO
YES
NO
YES
NO

 

⚙️ 코드

#include <iostream>
#include <vector>
#include <string>

using namespace std;

string isVPS(const string& ps){
    stack<char> stk;
    
    // 받아온 ps 문자열 순회
    for(char ch : ps){
    	if(ch == '('){
            stk.push(ch);
        }
        
        // ')' 이면
        else{
            // 스택 비어있으면
            if(stk.empty()){
            	return "NO";
            }
            stk.pop();
        }
    }
    
    // 모든 문자열 순회 완료 후 남은 게 있으면 NO, 없으면 YES
    return stk.empty() ? "YES" : "NO";

}


int main(){
    int T;
    cin >> T;
    cin.ignore(); // cin 이후 엔터가 getline과 만나면 종료되므로 항상 ignore을 해야 함
    
    while(T--){
    	string ps;
        getline(cin, ps);
        cout << isVPS(ps) <<"\n";
    }
    return 0;
}

메모리: 2024 KB, 시간: 4 ms

 

 

🤔 코드 풀이

스택을 이용한다. 스택은 가장 처음에 넣은 데이터가 가장 나중에 빠지는 FILO(First-In-Last_Out) 특징과 가장 마지막에 들어온 데이터가 가장 마지막에 빠지는 LIFO(Last-In-First-Out) 특징을 가지고 있다. 

 

1. 먼저 T개의 문자열 데이터를 입력받는다.

2. 문자열을 순회하면서 스택에 넣고 뺀다.

• 여는 괄호일 경우 스택에 push 한다.
• 닫는 괄호일 경우 
  • 스택이 비어있으면 짝이 없으므로 올바른 VPS가 아니므로 NO
  • 스택이 비어있지 않으면 스택을 pop 한다. '(' 와 ')' 이 짝을 맺게 된다.

3. 문자열 순회가 끝난 후 최종적으로 스택이 비어있으면 여는 괄호가 모두 짝이 맺어진 올바른 VPS라는 뜻이므로 YES 아니면 NO

 

⏱️ 코드 시간 복잡도

코드의 시간 복잡도는 O(TN) 이다.

 

순회 연산: 

isVPS 함수는 루프를 통해 문자열의 모든 문자를 순회한다. 

문자열의 길이를 n이라고 하면, 문자열 순회의 시간 복잡도는 O(n)이다.

 

스택 연산: 

• 여는 괄호를 만날 때마다 실행되는 스택의 push연산의 시간 복잡도는 O(1)이다.
• 닫는 괄호가 들어올 때마다 실행되는 스택의 pop연산의 시간 복잡도는 O(1)이다.
• 스택이 비어있는지 확인하는 empty연산의 시간 복잡도는 O(1)이다.

main 함수에서 T의 개수만큼 isVPS 함수를 호출한다.

isVPS 함수의 시간 복잡도는 O(n)이므로, 각 문자열 길이의 합을 N이라고 하면 시간복잡도는 O(TN)이다.

 

✨ 추가 공부

1. 

cin을 이용하여 정수를 입력받으면 마지막에 엔터로 인해 '\n' 문자가 남게 된다. 

이 문자가 getline함수와 만나게 되면 입력을 종료한다고 판단하고 비어있는 문자열을 반환하게 된다.

따라서 cin 이후  cin.ignore()을 이용하여 개행문자를 지워줘야 한다.

 

2. 

getline 함수는 C++ 표준 라이브러리로, 한 줄의 텍스트를 읽을 때 사용한다.

공백을 포함한 한 줄 전체를 읽어 들일 수 있어, 공백이 포함된 텍스트 입력을 처리할 때 유용하다.

입력을 받기 전 cin.ignore()을 이용하여 개행문자를 지워줘야 한다.

 

기본 사용법:

std::string line;
std::getline(std::cin, line);

입력 스트림 cin과 입력할 텍스트를 저장할 string 객체를 사용한다.

'\n' 개행문자 기준으로 문자열을 읽는다.

 

구분자 응용 사용법:

std::string line;
char delimiter = ',';
std::getline(std::cin, line, delimiter);

 

','를 구분자로 이용하여 입력을 읽을 수 있다.

쉼표를 입력하거나 엔터 키를 누를 때까지 입력된 모든 문자를 line에 저장한다.