← 목록으로

퍼즐 콤보

1차원 퍼즐 게임을 다음과 같은 규칙으로 만들어 보려고 한다.

예를 들어 AABBBAACCCAA라는 퍼즐을 고려하자. 이 퍼즐에는 BBB와 CCC인 색체인 두 개가 있다. 이 두 개의 색체인이 삭제되면 콤보가 한번 발생하고, 퍼즐은 AAAAAA가 된다. 이 퍼즐에는 AAAAAA인 색체인 하나가 있고, 이 색체인이 삭제되면 콤보가 한번 발생한다. 퍼즐의 모든 블록은 삭제되어 색체인이 없기 때문에 작업이 종료된다.

퍼즐이 주어졌을 때, 콤보의 발생 횟수와 남은 퍼즐을 출력하는 프로그램을 작성하라.

입력 형식

첫째 줄에 퍼즐의 길이를 나타내는 자연수 N이 주어진다. (1 ≤ N ≤ 1,000,000) 다음 줄에 길이 N인 퍼즐 문자열이 주어진다.

출력 형식

출력의 첫 줄에는 콤보의 발생 횟수를 출력한다. 다음 줄에 남은 퍼즐을 출력한다. 남은 퍼즐에 블록이 없을 경우에는 'PERFECT!!!' 를 출력한다.

입력 예제 1

12
AABBBAACCCAA

출력 예제 1

2
PERFECT!!!

입력 예제 2

15
AABBCCCBBAABBCC

출력 예제 2

3
BBCC

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

해설