c언어 9012번 괄호 (백준)

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

9012번: 괄호

#include <stdio.h>
#include <string.h>

int main(void)
{
	int t = 0; //테스트케이스
	scanf("%d", &t);
	
	while(t--)
	{
		char s[52] = ""; //char s[52] = {0}; 문자열 배열 초기화
		scanf("%s", s); //입력
		
		int left = 0; // ( 갯수
		int right = 0; // ) 갯수
		int len = strlen(s); //문자열 길이
		
		int i = 0;
		for(i = 0; i<len; i++)
		{
			if(s[i] == '(') left++; //갯수 증가
			if(s[i] == ')') right++; //갯수 증가
			
			if(left<right) { //만약 오른쪽 개수가 더 많다면 VPS가 아니다.
				printf("NO\n");
				break;
			}
		} //VPS이러면 (, )의 개수가 같으며, 왼쪽에서 오른쪽으로 이동 시에 )이 (보다 많아서는 안된다
		if(i==len && left==right) printf("YES\n");
		if(i==len && left!=right) printf("NO\n");
	}
	return 0;
}

 

풀이

 

VPS 조건

 

1. '('와 ')'의 개수는 같아야 한다.

2, 왼쪽에서 오른쪽으로 이동하면서, ')'의 개수가 '('을 초과해서는 안된다.

 

left은 '('의 개수, right은 ')'의 개수로 보면,

 

ex) (()())    

left = 1 -> left = 2 -> left = 2, right = 1-> left = 3, right = 1 -> left = 3, right = 2 -> left = 3, right = 3이므로

위의 VPS 조건을 만족한다.

 

ex) ()))((()

left = 1 - > left = 1, right = 1 -> left =1, right = 2 이므로

VPS조건의 2을 위배되므로, 위의 괄호들은 VPS가 아니다!!!

 

ex) (((())

이 경우는 (이 더 많으므로 VPS가 아니다!!! (VPS조건의 1을 위배)