24548번 - 도로 정보

현대오토에버는 국내 최초로 차량 운전 지원용 지도 생성을 위한 MMS (Mobile Mapping System) 기반 정밀지도 구축 시스템을 도입했다. 이는 고성능 레이저 스캐너 장치인 라이다 (LiDAR) 를 포함한 다양한 센서를 활용하여, 도로 및 주변 지형 등의 정보를 빠짐없이 취득하는 최첨단 3차원 공간정보 조사 시스템이다. 이 지도 정보를 활용하면 운전자에게 여러 편의 기능을 제공해줄 수 있다. 예를 들어 운전자에게 고성능 내비게이션 서비스를 제공할 수도 있고, 더 나아가 자율 주행에 필요한 도로 교통 정보를 제공해 줄 수도 있게 된다.

현대오토에버의 연구원 알정이는 오늘 정밀지도 정보 수집 차량으로부터 특정 시내의 도로를 촬영한 데이터를 전달받았다. 이 데이터에는 도로 주변의 나무, 잔디, 울타리 그리고 사람들을 촬영한 내용이 담겨 있다. 알정이는 이를 내비게이션 시스템에 사용할 수 있는 데이터로 가공할 것이다. 본격적인 작업에 앞서 알정이는 전달받은 데이터의 특성을 파악해보려고 한다.

도로 데이터를 전부 보고 있을 시간은 없으므로 알정이는 도로의 흥미로운 구간 하나를 뽑아서 보려고 한다. 도로는 나무를 나타내는 T, 잔디를 나타내는 G, 울타리를 나타내는 F 혹은 사람을 나타내는 P 로 이루어진 길이 $N$의 문자열로 표현된다. 도로 구간이란 도로의 연속된 일부분을 의미하며, 도로의 연속 부분 문자열로 표현된다. 흥미로운 구간이란, 길이가 1 이상인 도로 구간 중 그에 속한 모든 물체의 수가 3의 배수인 것을 의미한다. 예를 들어 도로 구간에 나무 3개, 울타리 3개가 담겼다면 그 도로 구간은 흥미로운 구간이지만, 나무 3개와 울타리 2개가 담겼다면 이는 흥미로운 구간이 아니다.

도로의 정보가 주어졌을 때, 흥미로운 구간이 될 수 있는 도로 구간의 개수를 구해보자.

첫 번째 줄에 정수 $N$이 주어진다. ($1 \leq N \leq 100\,000$ )

두 번째 줄에 도로를 표현한 길이 $N$의 문자열이 주어진다.

첫 번째 줄에 흥미로운 구간의 개수를 출력한다.