SCSC 기차 놀이

시간 제한1초메모리 제한1024 MB

요약

2, 5, [, ]로 이루어진 기차 설계도가 주어질 때 차량을 빈틈없이 이었을 때 생기는 기차간의 총 개수를 구한다.

난이도: 보통10점 중 6점
유형: 문자열, 스택, 누적 합, 구현
정답자: 아직 제출이 없습니다

문제

기차를 좋아하는 SCSC 부원 연호는 S와 C 모양을 한 줄로 이어 기차를 만들어 보고자 한다. 연호가 기차를 만드는 데에 사용할 S와 C 모양 차량들은 다음 그림과 같다.



그림1. S-5 모양 차량	그림2. C-[ 모양 차량	그림3. S-2 모양 차량	그림4. C-] 모양 차량

연호가 차량을 일렬로 빈틈없이 연결할 때 차량의 벽으로 구분되는 각각의 공간을 기차간(汽車間)이라고 한다. 이때 연호는 자기가 만든 SCSC 기차가 총 몇 개의 기차간을 가지게 될지 궁금해졌다. 연호의 SCSC 기차 설계도가 주어질 때, SCSC 기차가 총 몇 개의 기차간을 가지게 될지 구해보자!

입력

첫째 줄에 SCSC 기차 설계도에 포함된 차량의 수를 나타내는 정수 $N$ 이 주어진다. $(2 \le N \le 200\\,000)$

둘째 줄에 문자열 2, 5, [, ]로 이루어진 연호의 SCSC 기차 설계도가 주어진다.

설계도의 처음은 반드시 [로 시작하고, 끝은 반드시 ]로 끝난다.

출력

첫째 줄에 연호의 설계도에 따라 만들어질 SCSC 기차의 기차간 총 개수를 출력한다.

예제3

예제 1
입력
```
4
[52]
```
예상 출력
```
3
```
예제 2
입력
```
7
[22552]
```
예상 출력
```
8
```
예제 3
입력
```
4
[][]
```
예상 출력
```
2
```