전구 상태 바꾸기

면접 대비

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

요약

N개의 전구가 R, G, B 색으로 한 줄에 놓여 있습니다. 연속한 세 전구의 색을 한 단계씩 바꾸는 연산으로 모든 전구를 같은 색으로 만드는 최소 횟수를 구합니다.

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

문제

$N$ 개의 전구가 일렬로 놓여 있고, 각 전구는 빨간색, 초록색, 파란색 중 하나의 색으로 빛나고 있다. 지원이는 $N$ 개의 전구 중 연속한 세 개의 전구를 골라 그 전구들의 상태를 바꿀 수 있다. 전구의 상태를 바꾼다는 것은 빨간색 전구는 초록색으로, 초록색 전구는 파란색으로, 파란색 전구는 빨간색으로 바꾼다는 뜻이다.

연속한 세 전구의 상태를 바꾸는 과정을 반복해서 모든 전구가 같은 색으로 빛나게 하려면, 이 과정을 최소 몇 번 수행해야 하는지 구하여라.

입력

첫째 줄에 전구의 개수 $N(3\le N\le 100\,000)$ 이 주어진다.

둘째 줄에 각 전구가 빛나는 색을 나타내는 길이 $N$ 의 문자열 $S$ 가 주어진다. $S$ 의 $i$ 번째 문자는 $i$ 번째 전구의 색이다. $S$ 는 대문자 R, G, B로만 이루어져 있으며, R은 빨간색, G는 초록색, B는 파란색을 뜻한다.

출력

모든 전구가 같은 색으로 빛나게 하기 위해 연속한 세 전구의 상태를 바꾸는 과정을 최소 몇 번 수행해야 하는지 출력한다.

모든 전구를 같은 색으로 만들 수 없다면 -1을 출력한다.

예제3

예제 1
입력
```
4
RGGB
```
예상 출력
```
3
```
예제 2
입력
```
5
BGRGB
```
예상 출력
```
3
```
예제 3
입력
```
3
BRR
```
예상 출력
```
-1
```