카페 받침 정리대

문제

카페에서는 세척을 마친 컵 받침을 좁은 정리대에 차례대로 올린다. 받침에는 네 가지 무늬가 있으며, 각 무늬를 대문자 A, B, C, D로 나타낸다. 정리대에는 받침을 한 줄로 쌓을 수 있고, 맨 위에 놓인 받침만 확인하거나 꺼낼 수 있다. 작업을 시작하기 전에는 정리대가 비어 있다. 직원은 전달받은 순서대로 받침을 하나씩 처리한다. 새 받침을 처리할 때 정리대가 비어 있으면 그 받침을 올린다. 정리대가 비어 있지 않으면 새 받침의 무늬와 현재 맨 위 받침의 무늬를 비교한다. 두 무늬가 다르면 새 받침을 맨 위에 올린다. 두 무늬가 같으면 맨 위 받침을 꺼내 새 받침과 함께 보관 상자로 옮긴다. 이 경우 새 받침은 정리대에 올라가지 않으며, 정리대에 남아 있는 다른 받침도 추가로 꺼내지 않는다. 보관 상자로 옮긴 받침은 이후 작업에 다시 사용하지 않는다. 한 받침의 처리가 끝난 뒤에 다음 받침을 처리하므로, 앞선 작업에서 맨 위 받침이 사라졌다면 그 아래에 있던 받침이 다음 비교의 대상이 된다. 전달받은 받침의 순서를 바꾸거나, 서로 떨어져 있는 같은 무늬의 받침을 임의로 골라 보관 상자로 옮길 수는 없다. 직원은 모든 작업이 끝난 뒤 정리대에 남은 받침을 아래에서 위로 읽어 기록하려 한다. 받침이 전달되는 순서를 나타내는 문자열이 주어질 때, 정해진 규칙을 모두 적용한 뒤 남은 받침의 수와 무늬의 순서를 구하는 프로그램을 작성한다. 남은 받침이 하나도 없으면 무늬의 순서 대신 EMPTY를 기록한다.

입력

첫째 줄에 받침의 수를 나타내는 정수 N이 주어진다. 1 ≤ N ≤ 100,000이다.
둘째 줄에 길이가 N인 문자열 S가 주어진다. S의 각 문자는 A, B, C, D 중 하나이며, 왼쪽부터 받침이 전달되는 순서를 나타낸다.

출력

첫째 줄에 정리대에 남은 받침의 수를 출력한다. 둘째 줄에 남은 받침의 무늬를 아래에서 위 순서로 이어 붙여 출력한다. 남은 받침이 없으면 둘째 줄에 EMPTY를 출력한다.

8
ABBAACCD

2
AD

6
ABCCBA

0
EMPTY

5
ABCDA

5
ABCDA

출처: Devin.KR 자체 제작