거치대 스캔 정리

문제

공유 자전거 거치대의 점검 단말기는 작업자가 확인한 점검 항목을 영문 소문자 하나로 기록한다. 같은 문자는 같은 점검 항목을 뜻하며, 서로 다른 문자는 서로 다른 항목을 뜻한다. 한 번의 점검이 끝나면 단말기는 기록한 문자들을 시간순으로 이어 붙인 문자열을 운영 서버로 보낸다. 서버는 이 문자열을 정리하여 최종적으로 남길 점검 기록을 만든다. 이 단말기에는 같은 항목을 연속으로 두 번 확인하면 두 확인을 모두 취소하는 규칙이 있다. 서버는 받은 문자열을 왼쪽부터 한 글자씩 읽는다. 새로 읽은 문자가 현재 남아 있는 기록의 마지막 문자와 같으면, 마지막 문자를 지우고 새 문자도 남기지 않는다. 현재 기록이 비어 있거나 마지막 문자가 새 문자와 다르면, 새 문자를 현재 기록의 맨 뒤에 붙인다. 각 문자를 처리한 뒤의 기록을 기준으로 다음 문자를 처리한다. 취소는 문자의 종류별로 한꺼번에 적용하지 않는다. 두 문자가 전체 문자열에서 같은 횟수만큼 나타났다는 이유로 서로 취소되는 것도 아니다. 오직 새 문자를 읽는 순간에 남아 있는 기록의 마지막 문자만 비교한다. 앞선 취소 때문에 원래 떨어져 있던 문자들이 이어질 수 있으며, 그 결과는 이후 문자 처리에 그대로 반영한다. 예를 들어 기록이 ab인 상태에서 b를 읽으면 a만 남고, 그다음 a를 읽으면 기록이 비게 된다. 운영 담당자는 원본 문자열 대신 이 규칙으로 정리한 결과를 보관하려 한다. 모든 문자를 정확히 한 번씩 순서대로 처리한 뒤 남아 있는 문자열을 구하는 프로그램을 작성한다. 남은 문자의 순서를 바꾸면 안 된다. 문자가 하나도 남지 않았다면 빈 줄 대신 지정된 대문자 문자열 EMPTY를 출력한다.

입력

첫째 줄에 원본 문자열 S가 주어진다. S는 영문 소문자로만 이루어지며, 길이는 1 이상 100,000 이하인 정수다. 문자열 안에는 공백이 없다.

출력

정리한 문자열을 한 줄에 출력한다. 남은 문자가 없다면 EMPTY를 출력한다.

abccbad

d

aabccb

EMPTY

abaca

abaca

출처: Devin.KR 자체 제작