6045 : LRU 캐시 구현
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
캐시 교체 알고리즘 중 하나인 LRU (Least Recently Used) 캐시를 스택 구조와 해시 테이블을 활용해 시뮬레이션하십시오.
크기가 $K$인 캐시가 있고 데이터 요청 번호 리스트가 들어옵니다.
각 요청에 대해 캐시에 정보가 있으면
캐시가 꽉 찬 상태에서
[제약 조건]
• 캐시 용량 $K$: $1 \le K \le 100$ (정수)
• 요청 수 $N$: $1 \le N \le 10{,}000$ (정수)
크기가 $K$인 캐시가 있고 데이터 요청 번호 리스트가 들어옵니다.
각 요청에 대해 캐시에 정보가 있으면
HIT, 없으면 MISS를 반환하고 캐시를 업데이트합니다.캐시가 꽉 찬 상태에서
MISS가 발생하면 가장 오랫동안 참조되지 않은 데이터를 캐시에서 제거(Evict)합니다.[제약 조건]
• 캐시 용량 $K$: $1 \le K \le 100$ (정수)
• 요청 수 $N$: $1 \le N \le 10{,}000$ (정수)
입력 설명
첫째 줄에 캐시 용량 $K$가 주어집니다. ($1 \le K \le 100$)
둘째 줄에 공백으로 구분된 $N$개의 요청 번호들이 주어집니다. ($1 \le N \le 10,000$, 각 번호는 자연수)
둘째 줄에 공백으로 구분된 $N$개의 요청 번호들이 주어집니다. ($1 \le N \le 10,000$, 각 번호는 자연수)
출력 설명
각 요청에 대해
마지막 줄에는 모든 처리가 끝난 후의 최종 캐시 상태를 가장 최근에 사용된(MRU) 순서부터 오래된(LRU) 순서로 공백 구분 출력합니다.
HIT 또는 MISS 결과를 한 줄에 하나씩 출력합니다.마지막 줄에는 모든 처리가 끝난 후의 최종 캐시 상태를 가장 최근에 사용된(MRU) 순서부터 오래된(LRU) 순서로 공백 구분 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3
1 2 3 1 4 5
출력 예시
COPY
복사되었습니다!
복사되었습니다!
MISS
MISS
MISS
HIT
MISS
MISS
5 4 1도움
캐시를 관리하는 리스트의 끝에 새로운/최근 접근 데이터를 추가(MRU)하고, 꽉 찼을 때 리스트의 첫 번째 원소(LRU)를 pop합니다. 캐시 내 위치 업데이트가 빈번하므로 순서가 유지되는 OrderedDict나 리스트 연산을 적절히 씁니다.