c언어 10799번 쇠막대기 (백준)

#include <stdio.h>

int main(void)
{
	char s[100001] = {}; //문자열을 받을 배열
	scanf("%s", s); //입력
	int left = 0, ans = 0; //left는 (의 개수, ans는 쇠막대기의 개수
	
	for(int i=0; s[i] != 0; i++) { //\0이 나오기 전까지
		if(s[i] == '(') left++; //(이면 left 증가
		else { // ) 일 때 
			--left; //( 1개 감소
			if(s[i-1] == '(') ans += left; //() 형태 즉 레이저 일 때
			else ans++; //쇠막대기의 끝이었을 때
		}
	}
	printf("%d", ans); //출력
    return 0;
}

풀이 : 스택

 

( 은 쇠막대기의 시작이거나, 레이저의 시작입니다.

) 은 쇠막대기의 마지막이거나, 레이저의 마지막입니다.

 

(이 나올 때는 (의 개수를 세는 변수를 +1 해주며

 

)이 나오면 (의 개수를 담는 변수를 -1 한다음

) 이 쇠막대기의 마지막인지, 레이저의 마지막인지를 이전의 데이터를 이용해서 판단합니다.

 

만약 레이저라면, 이전까지 존재하던 쇠막대기들의 개수만큼 ans에 추가하며

만약 쇠막대기의 마지막이라면, 레이저로 자르지 않아도 하나의 토막으로 볼 수 있기 때문에, ans에 +1을 합니다.

 

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

10799번: 쇠막대기

 

예제 입력 2번을 그림으로