문제 링크 : https://www.acmicpc.net/problem/10799

쇠막대기를 레이저()로 절단할 때 잘려진 조각의 총 개수를 출력하는 문제
쇠막대기의 시작은 (, 끝은 )로 구분한다.

풀이 과정

그림을 그려보며 레이저로 쇠막대기가 잘릴 때 잘린 조각이 몇 개가 나오는지 알 수 있다. 쇠막대기 조각 수를 세는 방법을 그림을 통해 확인해보자

코드 (C++/C)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

using namespace std;

int main(void)
{
	char command[100000] = { 0, };
	scanf("%s", command);
	int n = strlen(command);
	
	char stack[100000];
	int pos = 0;

	int cnt = 0;

	for (int i = 0; i < n; i++)
	{
		if (command[i] == '(')
		{
			stack[pos++] = command[i]; //스택에 추가
		}
		else //닫는 괄호
		{
			if (command[i - 1] == '(') //레이저
			{
				pos--;
				cnt += pos;
			}
			else //쇠막대기
			{
				pos--;
				cnt += 1;
			}
		}
	}
	printf("%d", cnt);
}

코드 (python)

stick = input()

stack = []
cnt = 0 #합계
sticks = 0 #쇠막대기 수
n = len(stick) #총 개수

for i in range(n):
    if stick[i] == '(':
        stack.append(stick[i])
        #sticks += 1
    else:  # )인 경우 -> 쇠막대기 끝 or 레이저
        stack.pop()
        if stick[i-1] == '(': #레이저
            cnt += len(stack)
            #sticks -= 1
        else: #쇠막대기 끝
            cnt +=1
print(cnt)