[알고리즘 문제풀이] 8. 올바른 괄호

 

'('의 개수와 ')'의 개수가 같을 때 YES, 다를 때 NO 출력해주면 된다.

 

와, 근데 )))((( 이런 경우는 안되잖아 빼먹을 뻔했네

배열을 앞에서부터 읽어나갈 때

'('의 개수에 비해 ')'의 개수가 커지면 NO가 되겠네

#include <stdio.h>
using namespace std;
	
int main(){
	
	//freopen("input.txt", "rt", stdin);
	
	// 1. 문자열을 입력받는다.
	char array[30]; 
	scanf("%s", &array);
	

	// 2. 각 다른 괄호의 갯수를 센다.
	// 왼쪽 괄호, 오른쪽 괄호의 갯수를 정의한다.
	int left, right = 0; 
	for( int i = 0; array[i] != '\0'; i++){
		if(array[i] == '('){
			left++;
		}
		else right++;
		
		if(left < right){
			left = 100;
		}
	} 
	
	// 3. 괄호의 갯수가 같으면 YES 출력, 다르면NO 출력
	if( left == right ) printf("YES\n");
	else printf("NO\n");
	 
	return 0;
}

이렇게 해도 100점이 나온다.

 

중간에 왼, 오 괄호 수가 같더라도 ))(( 이런 경우를 추가하기 위해

if(array[i] == '('){
			left++;
		}
		else right++;
		
		if(left < right){
			left = 100;
		}

를 넣었다.

 

---

해설은 다른 방식으로 풀었다.

왼괄호가 나오면 +1, 오른쪽 괄호가 나오면 -1 해주고

음수가 나오는 순간, 아예 for에서 break를 걸어준다.

0이 되었을 때 YES. 나머진 NO

#include <stdio.h>
using namespace std;
int main(){
	//freopen("input.txt", "rt", stdin);
	
	// 1. 문자열을 입력받는다.
	char array[30]; 
	scanf("%s", &array);
	

	// 2. 각 다른 괄호의 갯수를 센다.
	int cnt = 0; 
	for( int i = 0; array[i] != '\0'; i++){
		if(array[i] == '('){cnt++;}
		else cnt--;
		
		if(cnt < 0) break;
	} 
	
	// 3. cnt가 0이면 YES 출력, 다르면NO 출력
	if( cnt == 0 ) printf("YES\n");
	else printf("NO\n");
	 
	return 0;
}

 

원래 이 문제는 스택을 사용하는 문제라고 한다.

현재 스택을 잘 모르니 패스~