[알골 90제] 37번 - LRU 카카오 캐시 문제 변형

1) Cache Miss : 해야할 작업이 캐시에 없는 상태로 위 상태에서 만약 새로운 작업인 5번 작 업을 CPU가 사용한다면 Cache miss가 되고 모든 작업이 뒤로 밀리고 5번작업은 캐시의 맨 앞에 위치한다. 
5 2 3 1 6
(7번 작업은 캐시에서 삭제된다.)

2) Cache Hit : 해야할 작업이 캐시에 있는 상태로 위 상태에서 만약 3번 작업을 CPU가 사용 한다면 Cache Hit가 되고, 63번 앞에 있는 5, 2번 작업은 한 칸 뒤로 밀리고, 3번이 맨 앞으
로 위치하게 된다. 
5 2 3 1 6 ---> 3 5 2 1 6
캐시의 크기가 주어지고, 캐시가 비어있는 상태에서 N개의 작업을 CPU가 차례로 처리한다면 N개의 작업을 처리한 후 캐시메모리의 상태를 가장 최근 사용된 작업부터 차례대로 출력하는 프로그램을 작성하세요.

 

▣ 입력설명

첫 번째 줄에 캐시의 크기인 S(3<=S<=10)와 작업의 개수 N(5<=N<=1,000)이 입력된다. 두 번째 줄에 N개의 작업번호가 처리순으로 주어진다. 작업번호는 1 ~100 이다.
▣ 출력설명

마지막 작업 후 캐시메모리의 상태를 가장 최근 사용된 작업부터 차례로 출력합니다.
▣ 입력예제 1                                  
5 9 1 2 3 2 6 2 3 5 7
▣ 출력예제 1
7 5 3 2 6

// 37번 - LRU 카카오 캐시 문제 변형

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

int main() {

	int s, n, a, pos;

	scanf("%d %d", &s, &n);
	vector<int> c(s); //캐시공간

	for (int i = 0; i < n; i++) {
		scanf("%d", &a); //값 받기
		pos = -1; //hit or miss 확인용
		for (int j = 0; j < s; j++) {
			if (a == c[j])//hit
				pos = j;
		}
		if (pos == -1) { //miss
			for (int j = s - 1; j >= 1; j--)
				c[j] = c[j - 1];
		}
		else { //hit
			for (int j = pos; j >= 1; j--) 
				c[j] = c[j - 1];
		}
		c[0] = a;
	}
	for (int i = 0; i < s; i++)
		printf("%d ", c[i]);
	return 0;
}