채팅방 캐시 정리

문제

사내 메신저 서버는 직원들이 최근에 연 채팅방의 메시지 묶음을 메모리 캐시에 보관한다. 캐시에는 채팅방을 최대 K개까지 담을 수 있고, 가장 오래전에 사용한 방부터 밀어내는 방식(LRU)으로 운영한다. 서버는 요청을 받은 순서대로 처리한다. 요청은 두 종류이다. 'O x'는 x번 채팅방을 여는 요청이다. 방이 캐시에 있으면 적중으로 세고 그 방을 가장 최근에 사용한 것으로 바꾼다. 없으면 실패로 세고 저장소에서 읽어 와 캐시에 가장 최근 방으로 넣는데, 이때 방이 K개를 넘으면 가장 오래전에 사용한 방 하나를 캐시에서 내보낸다. 'D x'는 x번 채팅방을 삭제하는 요청이다. 방이 캐시에 있으면 캐시에서 제거하고, 없으면 아무 일도 일어나지 않는다. 삭제 요청은 적중도 실패도 아니며, 사용 순서에도 영향을 주지 않는다. 삭제된 방 번호도 이후 다시 열릴 수 있으며, 그 경우 일반적인 열기 요청과 같이 처리한다. 처음 캐시는 비어 있다. 모든 요청을 처리한 뒤 적중 횟수와 실패 횟수, 그리고 캐시에 남은 방을 확인하려 한다.

입력

첫 줄에 K와 요청 수 Q가 공백으로 구분되어 주어진다. 이어 Q개의 줄에 요청이 'O x' 또는 'D x' 형태로 주어진다. 1 ≤ K ≤ 200,000, 1 ≤ Q ≤ 200,000, 1 ≤ x ≤ 10^9. 모든 값은 정수이다.

출력

첫 줄에 적중 횟수와 실패 횟수를 공백으로 구분해 출력한다. 둘째 줄에 캐시에 남은 채팅방 번호를 가장 최근에 사용한 것부터 공백으로 구분해 출력한다. 캐시가 비어 있으면 EMPTY를 출력한다.

2 7
O 1
O 2
O 1
O 3
O 2
D 1
O 4

1 5
4 2

1 6
O 7
O 7
D 7
O 7
D 8
D 7

1 2
EMPTY

출처: Devin.KR 자체 제작