c언어 25918번 북극곰은 괄호를 찢어 (백준)

#include <stdio.h>

int main(void)
{
	int n;
	scanf("%d", &n);
	
	char s[n+1];
	scanf("%s", s);	
	
	if(n&1) { //홀수 인 경우, 반드시 원하는 문자열을 만들 수가 없습니다.
		printf("-1");
		return 0;
	}
    
    //스택
	int cnt = 0, a=0, max=0; //cnt 스택의 끝에서 다음칸을 가리킵니다, a=현재 스택에서의 걸리는 날짜, max 최대 걸리는 날짜
	for(int i=0; i<n; i++) {
		a++; //1증가
		if(s[i] == '(') { 
			if(cnt && s[cnt-1] == ')') { //()이면 스택에서 제거 및, 걸리는 날도 -2 
				a-=2;
				--cnt;	
			} else s[cnt++] = '('; //스택에 넣기
		} else {
			if(cnt && s[cnt-1] == '(') { //)(이면 스택에서 제거 및, 걸리는 날도 -2
				a-=2;
				--cnt;
			} else s[cnt++] = ')'; //스택에 넣기
		}
		if(max < a) max = a; //최대 날짜
	}
	
	if(cnt) max = -1; //스택이 비어있지 않음 -> 원하는 문자열을 만들수 가 없음
	
	printf("%d", max);
}

풀이 : 스택

 

스택을 이용해서 (), )( 가 되는 경우를 스택에서 제거해 줍니다. 이 과정에서

최소 며칠이 걸리는 지를 알려면, 스택에 하나씩 요소를 넣으면서, 요소의 개수가 최대가 될때를 구하면 됩니다.

 

ex)

6

((()))

 

(

((

((( ---- 최대 3개

(( ()삭제

( ()삭제

()삭제

 

스택은 비어있고 최대 3개

 

또한 스택이 비어있지 않다면 원하는 문자열을 만들지 못했다는 의미입니다.

ex)

4

)))(

 

)

))

)))

)) )( 삭제

 

스택에 ))가 남았으며, 북극곰은
)) (( 의 방식으로는 찢질 못합니다.

 

 

고로 스택을 이용해서 최대 요소의 개수를 구하고, 스택이 비어있다면, 최대 요소의 개수를 출력

스택이 비어있지 않다면 -1을 출력합니다.

 

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

25918번: 북극곰은 괄호를 찢어