[C/C++] 코드업(codeup) 4833번 쇠 막대기

▽문제 바로가기

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

쇠 막대기

---

입력

한 줄에 쇠 막대기와 레이저의 배치를 나타내는 괄호 표현이 공백없이 주어진다. 괄호 문자의 개수는 최대 100,000이다.

 

출력

잘려진 조각의 총 개수를 나타내는 정수를 한 줄에 출력한다.

 

문제 풀이

 

스택을 이용해서 풀 수 있는 문제입니다.

 

열림 괄호 바로 뒤에 닫힘 괄호가 오면 레이저이고, 그 외 경우는 쇠파이프의 시작과 끝을 나타냅니다.

 

쇠파이프의 개수를 기록하면서 레이저를 만나면 쇠파이프의 개수만큼 더해줍니다.

 

쇠파이프의 조각은 하나의 쇠파이프가 만난 레이저수 +1입니다. 따라서, 쇠파이프가 끝날 때 +1을 해주면 조각의 총개수를 구할 수 있습니다. 문제에서 모든 쇠파이프는 최소 하나의 레이저를 만난다고 했으니 이런 접근이 가능합니다.

 

#include <stdio.h>

int main(){
	
	char arr[100001];
	int pipe = 0;
	
	int sum = 0;
	for(int i=0;;i++){
		scanf("%c", &arr[i]);
		if(arr[i]!='('&&arr[i]!=')') break;
		
		//열림괄호면 push 
		if(arr[i]=='(') ++pipe;
		
		//닫힘괄호면
		else{
			//pop하고
			--pipe;
			
			//레이져면 막대기갯수만큼 더함
			if(arr[i-1]=='(') sum += pipe;
			
			//쇠막대기 끝이면 1더하고 pop 
			else ++sum;
		}
		
	}
	
	printf("%d", sum);
	
}