[BOJ 백준] 9012 - 괄호 (C++)

문제 바로가기

https://www.acmicpc.net/problem/9012

9012번: 괄호

---

관련 알고리즘

- 해당 없음

---

정답 및 해설

괄호로 이루어진 문자열을 입력받아 문자열 내에서 괄호가 모두 닫히는지 확인하는 문제이다.

기본적으로 스택(Stack)이라는 자료구조를 활용하여 해결하는 문제이지만,

이번 풀이에는 간접적으로 비슷한 알고리즘을 구현하여 해결할 계획이다.

 

변수 N을 선언한 뒤, 문자열을 하나씩 확인하면서 '(' 일 경우 N++, ')' 일 경우 N-- 연산을 하도록 하면

현재 해결해야 할(열려있는 상태의, '()'짝을 이루지 못한)  괄호의 개수를 N으로 나타낼 수 있다.

문자열을 검사할 동안 N이 음수가 된다면 "())"와 같이 ')' 기호가 먼저 나온 것으로 해석할 수 있고,

문자열 검사를 종료한 후에 N이 양수라면 "(()"와 같이 아직 완료되지 않은 '(' 기호가 있는 것으로 해석한다.

---

C++

#include<bits/stdc++.h>
using namespace std;
int main(){
    int N=0,i,T;
    string L;
    cin>>T;
    while(T--){
        cin>>L;
        for(i=0,N=0; N>=0&&i<L.length(); i++){
            if(L[i]=='(') N++;
            else N--;
        }
        if(N==0) cout<<"YES\n";
        else cout<<"NO\n";
    }
}

 

Line	해설
4~5	int N : 문자열을 검사하면서 괄호 상태(개수)를 저장할 변수 int T : 테스트 케이스의 개수 string L : 입력받은 괄호로 이루어진 문자열
6	테스트 케이스의 개수(T)를 입력받는다.
7~15	while(T--) 문으로 테스트 케이스 개수만큼 반복에 들어간다. Line 8에서 반복문에 들어감과 동시에 문자열 L을 입력받는다.
9~12	for 반복문을 통해 문자열내의 각 문자를 검사한다. 초기식으로 i와 N을 0으로 설정하고, 조건식을 N>=0 && i<L.length() 으로 설정한다.1) if 조건문으로 L[i]가 '(' 이라면 N에 1을 더하고, 아니라면 1을 뺀다. 문자를 반복하면서 N이 음수가 되거나 문자열을 모두 확인했다면 조건식에 의해 반복문을 빠져나온다.
13~14	반복문 종료 후, N==0 이라면 모든 괄호 문자열이 VPS 상태이므로 "YES"를 출력한다. 아니라면 "NO"를 출력하여 정답을 구한다.

1) for문 내의 초기식, 조건식, 반복식에는 위처럼 여러 연산이 등장해도 무관하지만 코드의 가독성을 높이기 위해 지양하는 편이다.