[백준 9012번] 괄호

🔗알고리즘 문제

문제 이해는 빠르게 하였지만 코드로 작성하여 정답까지 가는 길이 오래 걸린 문제이다. 아직 stack을 활용한 문제풀이가 익숙하지 않아 string을 쌩으로 사용하여 문제를 해결하여 조금 오래걸린 것 같다,,,,

문제 분석

괄호로 이루어진 문자열이 입력으로 주어졌을 때 해당 문자열이 VPS인지 아닌지 판단하는 문제이다.

VPS란?
한 쌍의 괄호 기호로 된 "()"를 말한다.
만약 X가 VPS라면 ( X ) 도 VPS가 된다.

ex). 

())(() <- VPS가 아님
((())) <- VPS가 맞음

발상

주어진 문자열이 VPS라면 문자열에서 ( ) 쌍으로 이루어진 부분을 찾아 계속 지운다면 문자열이 모두 사라진다는 사실을 파악하였다.

이를 토대로 더이상 ( ) 쌍이 남아있지 않을 때까지 문자열을 for문으로 돌며 ( ) 쌍은 삭제시키고 for문이 끝난 후 문자열이 비어있다면 VPS 이고, 아니라면 VPS가 아니다. 라고 판단하였다.

알고리즘 설계

1. 입력받을 문자열의 수를 입력받는다.
2. 문자열을 입력받는다.
3. 문자열의 처음부터 for문을 진행한다.
4. ( ) 쌍을 발견했다면 문자열의 해당 부분을 삭제하고 for문의 인덱스를 한칸 당겨준다.
5. for문이 종료된 후 문자열이 비어있는지를 비교하여 VPS인지 확인하고 값을 출력한다.
6. 모든 문자열을 입력받을 때까지 반복한다.

코드

#include<iostream>
#include<string>

using namespace std;

bool IsVPX(string st);

int main(){
    int count;
    cin >> count;

    for(int i = 0; i < count; i++){
        string PS;
        cin >> PS;
        cout << ((IsVPX(PS)) ? "YES" : "NO") << "\n";
    }
}

bool IsVPX(string st){
    if(st[0] == ')' || st[st.length() - 1] == '(') return false;

    int lenght = st.length();
    for(int i = 0; i < lenght; i++){
        if(st[i] == '(' && st[i + 1] == ')'){
            st.erase(st.begin() + i);
            st.erase(st.begin() + i);

            i = -1;
        }
    }

    return (st.empty()) ? true : false;
}