Collecting Sogang

면접 대비

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

요약

소문자 문자열에서 s, o, g, a, n, g를 앞에서부터 순서대로 (연속할 필요 없이) 골라 "sogang"을 만들고 그 문자들을 제거하는 과정을 반복할 때 만들 수 있는 단어의 최대 개수를 구한다.

난이도: 보통10점 중 5점
유형: 그리디, 문자열, 구현
정답자: 아직 제출이 없습니다

문제

알파벳 소문자로 이루어진 문자열 $S$ 가 주어진다. 이 문자열에서 s, o, g, a, n, g 여섯 개의 문자를 문자열의 앞에서부터 순서대로 추출하여 sogang이라는 단어를 만들 수 있다. 이때, 이 여섯 개의 문자가 문자열에서 연속할 필요는 없다.

sogang단어를 완성할 때마다 상품 하나를 받는다. 사용된 문자는 문자열에서 제거되며, 제거된 자리의 뒷부분에 있는 문자들은 앞으로 당겨진다. 이 과정을 여러 번 반복할 때, 받을 수 있는 상품의 최대 개수를 구하시오.

입력

첫 번째 줄에 문자열의 길이에 해당하는 정수 $N$ 이 주어진다. ( $1 \le N \le 100\\,000$ )

두 번째 줄에는 알파벳 소문자로 구성된 길이가 $N$ 인 문자열 $S$ 가 주어진다.

출력

위의 규칙에 따라 단어를 만들 때, 받을 수 있는 상품의 최대 개수를 출력하여라.

예제5

예제 1
입력
```
6
soggan
```
예상 출력
```
0
```
예제 2
입력
```
12
ssooggangang
```
예상 출력
```
2
```
예제 3
입력
```
12
sogansgogang
```
예상 출력
```
2
```
예제 4
입력
```
12
soggsoagnang
```
예상 출력
```
1
```
예제 5
입력
```
5
abcde
```
예상 출력
```
0
```