LRU 캐싱

많은 양의 데이터에 접근하는 것이 너무 느리다고 판단될 때 흔히 쓰이는 속도 향상 기법은, 데이터의 일부를 캐시(cache) 라고 부르는 더 빠르게 접근할 수 있는 곳에 보관해 두는 것이다. 특정 데이터에 처음 접근할 때는 느린 방법을 써야 한다. 하지만 그 데이터를 캐시에 저장해 두면, 다음에 필요할 때는 훨씬 빠르게 접근할 수 있다. 예를 들어 데이터베이스 시스템은 하드 드라이브를 읽지 않아도 되도록 데이터를 메모리에 캐싱해 둘 수 있고, 웹 브라우저는 네트워크로 내려받지 않아도 되도록 웹 페이지를 로컬 컴퓨터에 캐싱해 둘 수 있다.

일반적으로 캐시는 필요할 수 있는 모든 데이터를 담기에는 너무 작다. 따라서 어느 시점에는 새 데이터를 넣을 자리를 만들기 위해 캐시에서 무언가를 제거해야 한다. 목표는 곧 다시 사용될 가능성이 높은 항목을 남겨 두는 것이다. 이를 위해서는 무엇을 제거할지 고르는 합리적인 알고리즘이 필요하다. 간단하지만 효과적인 알고리즘 하나가 바로 LRU(Least Recently Used, 가장 오래 전에 사용됨)이다. LRU 캐싱에서는 항상 가장 오래 전에 사용된 데이터를 버린다.

예를 들어 최대 다섯 개의 데이터를 담을 수 있는 캐시를 생각해 보자. 데이터 세 개 A, B, C에 접근한다고 하자. 각각에 접근할 때마다 캐시에 저장하므로, 이 시점에서 캐시에는 데이터 세 개가 있고 빈자리가 두 개 있다(그림 1). 이제 D와 E에 접근한다고 하자. 이들도 캐시에 추가되어 캐시가 가득 찬다. 다음으로 A에 다시 접근한다고 하자. A는 이미 캐시에 있으므로 캐시의 내용은 바뀌지 않지만, 이 접근도 한 번의 사용으로 간주되어 A가 가장 최근에 사용된 데이터가 된다. 이제 F에 접근하면 자리를 만들기 위해 무언가를 버려야 한다. 이 시점에서 가장 오래 전에 사용된 것은 B이므로, B를 버리고 그 자리에 F를 넣는다(그림 2). 여기서 다시 B에 접근하면, 처음 B에 접근했을 때와 똑같다. B를 가져와 캐시에 저장하고, 자리를 만들기 위해 가장 오래 전에 사용된 데이터(이번에는 C)를 버린다.

그림 1: A, B, C 접근 후의 캐시	그림 2: A, B, C, D, E, A, F 접근 후의 캐시

이 문제에서 당신이 할 일은 데이터 접근 순서를 입력받아 LRU 캐시를 시뮬레이션하는 것이다. 요청이 있을 때마다 캐시의 내용을 가장 오래 전에 사용된 것부터 가장 최근에 사용된 것 순서로 출력한다.

입력은 한 줄에 하나씩 주어지는 여러 개의 데이터 세트로 이루어진다. 각 데이터 세트는 정수 N과 두 글자 이상인 문자열로 구성된다. 정수 N은 해당 데이터 세트에서 캐시의 크기이다($1 \le N \le 26$). 문자열은 오직 대문자와 느낌표로만 이루어진다. 대문자는 해당 데이터에 대한 접근을 나타내고, 느낌표는 현재 캐시의 내용을 출력하라는 요청을 나타낸다.

예를 들어 ABC!DEAF!B!라는 순서는 다음을 의미한다. A, B, C에 (이 순서대로) 접근하고, 캐시의 내용을 출력하고, D, E, A, F에 (이 순서대로) 접근하고, 캐시의 내용을 출력하고, B에 접근한 뒤, 다시 캐시의 내용을 출력한다.

각 순서는 항상 대문자로 시작하며, 느낌표를 적어도 하나 포함한다.

입력의 끝은 숫자 0 하나만 있는 줄로 표시된다.

각 데이터 세트에 대해 먼저 "Simulation S" 줄을 출력한다. 여기서 S는 첫 번째 데이터 세트면 1, 두 번째면 2와 같이 매겨진다. 그다음, 데이터 세트의 느낌표마다 현재 캐시에 들어 있는 데이터를 한 줄에 하나의 문자열로 출력한다. 문자들은 가장 오래 전에 사용된 것부터 가장 최근에 사용된 것 순서로 정렬하며, 가장 오래 전에 사용된 것이 먼저 온다. 캐시에 들어 있는 문자만 출력한다. 캐시가 가득 차 있지 않다면 출력할 문자가 그만큼 적어질 뿐이다(빈칸은 출력하지 않는다). 각 순서는 항상 대문자로 시작하므로, 완전히 비어 있는 캐시를 출력하라는 요청은 결코 받지 않는다.