[C/C++] 코드업(codeup) 3129번 올바른 괄호 2

▽문제 바로가기

https://codeup.kr/problem.php?id=3129

올바른 괄호 2

---

입력

'('와 ')'로 이루어딘 괄호 문자열이 입력된다.(50,000글자 이하)

 

출력

올바른 괄호 문자열이면 "good", 올바른 괄호 문자열이 아니면 "bad"를 출력하시오.

 

문제 풀이

 

괄호가 틀릴 경우는 두 가지입니다.

 

1. 닫힌 괄호가 먼저 나온 경우

2. 열림 괄호가 많이 나온 경우

 

스택으로 구현하면서 풀 수 있습니다. 실제 스택처럼 구현할 필요는 없고 top값을 참고하여 풀었습니다.

열림 괄호는 top증가, 닫힘 괄호는 top감소를 하였습니다.

 

더 이상 스택이 없는 상태에서 pop이 일어나면 닫힘 괄호로 인해 틀렸을 경우이고

전체 입력을 다 계산했을 때 top이 -1이 아니라면(스택이 쌓여있다면) 열림 괄호로 인해 틀린 경우입니다.

 

#include <stdio.h>

int main(){
	
	char arr[50001];	//입력 50,000글자 이하
	bool isGood = true;	//닫힘 괄호로인해 틀렸을 때 
	gets(arr);	//입력 
	
	int top = -1;
	for(int i=0;;i++){
		if(arr[i]!='('&&arr[i]!=')') break;
		
		if(arr[i]=='(') top++;
		
		if(arr[i]==')') top--;
		
		//닫힘 괄호로인해 틀렸을 때
		if(top==-2){
			isGood = false;
			break;
		}
	}
	
	if(!isGood) printf("bad");	//닫힘 괄호로인해 틀렷을 때 
	else if(top!=-1) printf("bad");	//열림 괄호로인해 틀렸을 때
	else printf("good");
	
}