Written by JS970
on
on
9012 - 괄호
- 난이도: 실버 4
- 날짜: 2023년 2월 5일
- 상태: Correct
- 추가 검토 여부: Yes
solution
- depth라는 변수를 설정하고, 입력받은 문자열에 대해 왼쪽부터 오른쪽까지 문자를 탐색한다.
- 좌괄호가 인식되었을 경우 depth를 1만큼 증가시키고, 우괄호가 인식되었을 경우 depth를 1만큼 감소시킨다.
- 문자열 판별 연산 중 depth가 음수가 된 경우 이는 필요 없는 우괄호가 입력이 더 된 경우이므로 NO를 출력한다.
- 문자열 판별 연산이 끝난 후 depth가 0이 아닌 경우 필요 없는 좌괄호가 입력이 더 된 경우이므로 NO를 출력한다.
- 이 이외의 경우 입력된 문자열이 VPS이므로 YES를 출력한다.
- 문제 설명의 알고리즘 분류에 따르면 본 문제는 stack 자료구조를 사용하여 해결할 수도 있다. 다음에는 이 방법으로 시도해보자.
code
#include <iostream>
#include <string>
using namespace std;
int main()
{
string input;
int T;
cin >> T;
int depth;
bool vps;
for(int i = 0; i < T; i++)
{
depth = 0;
vps = true;
cin >> input;
for(int j = 0; j < input.size(); j++)
{
if(input[j] == '(') depth++;
else depth--;
if(depth < 0)
{
vps = false;
break;
}
}
if(!vps || depth > 0) cout << "NO" << endl;
else cout << "YES" << endl;
}
return 0;
}