겹쳐 붙은 배송 표식

문제

택배 분류장에서는 상자에 붙은 배송 표식을 한 줄의 문자열로 기록한다. 표식 하나는 알파벳 대문자 하나로 나타내며, 같은 글자는 같은 분류 구역을 뜻한다. 상자가 여러 분류 구역을 거치는 동안 표식이 중복해서 붙는 일이 생겨, 출고 전에 정해진 규칙으로 기록을 정리하기로 했다. 정리 장치는 입력 문자열의 표식을 왼쪽부터 하나씩 읽는다. 장치에는 처음에 비어 있는 보관 줄이 있으며, 보관 줄에는 지금까지 남겨 둔 표식이 순서대로 들어 있다. 새 표식을 읽었을 때 보관 줄이 비어 있으면 그 표식을 보관 줄의 맨 뒤에 붙인다. 보관 줄이 비어 있지 않으면 맨 뒤의 표식과 새 표식을 비교한다. 두 표식이 같으면 맨 뒤의 표식을 제거하고 새 표식도 버린다. 두 표식이 다르면 새 표식을 맨 뒤에 붙인다. 표식 두 개가 함께 사라져도 이미 읽은 표식을 다시 읽지는 않는다. 다음 입력 표식을 읽을 때는 그 시점에 보관 줄의 맨 뒤에 있는 표식과 비교한다. 따라서 중간의 표식들이 사라진 결과, 원래 문자열에서 떨어져 있던 표식이 이후의 비교에 영향을 줄 수 있다. 보관 줄에 남은 표식들의 상대적인 순서는 바뀌지 않는다. 예를 들어 입력이 ABBA이면 A와 B가 차례로 보관된다. 세 번째 표식 B가 들어오면 보관된 B와 함께 사라지고, 마지막 A도 보관된 A와 함께 사라진다. 모든 입력 표식을 정확히 한 번씩 처리한 뒤 보관 줄에 남는 문자열을 구해야 한다. 아무 표식도 남지 않은 경우에는 빈 줄 대신 지정된 문자열 EMPTY를 출력한다.

입력

첫째 줄에 표식의 개수 N이 주어진다. N은 1 이상 200,000 이하의 정수다.
둘째 줄에 길이가 정확히 N인 문자열 S가 주어진다. S의 모든 문자는 알파벳 대문자 A부터 Z까지 중 하나이며, 공백은 없다.

출력

정리가 끝난 뒤 보관 줄에 남은 표식들을 앞에서부터 이어 붙인 문자열을 한 줄에 출력한다. 남은 표식이 없으면 EMPTY를 출력한다.

5
ABBAC

C

8
ABCCBAAA

EMPTY

출처: Devin.KR 자체 제작