섹션6. Sort - 4. Least Recently Used

📌 문제 설명

캐시 메모리는 CPU와 주기억장치 사이에서 자주 사용하는 데이터를 빠르게 접근하기 위한 장치입니다.
하지만 용량이 작기 때문에 효율적으로 관리하는 알고리즘이 필요합니다.

LRU (Least Recently Used) 알고리즘은 가장 오랫동안 사용되지 않은 데이터를 제거하는 방식입니다.
N개의 작업 요청이 들어왔을 때, 캐시 크기가 S일 경우 마지막 작업 후 캐시 상태를 구하세요.
결과는 가장 최근 사용된 작업부터 순서대로 출력해야 합니다.

---

📝 입력 & 출력

입력

• 첫 줄: 캐시 크기 S (3 ≤ S ≤ 10), 작업 개수 N (5 ≤ N ≤ 1000)
• 두 번째 줄: N개의 작업 번호 (1 ~ 100 사이 자연수)

출력

• 마지막 작업 이후의 캐시 상태를 가장 최근 사용된 작업부터 출력

---

🔹 예제 입력 & 출력

예제 입력 1

5 9
1 2 3 2 6 2 3 5 7

 

예제 출력 1

7 5 3 2 6

 

힌트

작업번호    캐시 상태
--------    -----------------------------
1           1 0 0 0 0
2           2 1 0 0 0
3           3 2 1 0 0
2           2 3 1 0 0
6           6 2 3 1 0
2           2 6 3 1 0
3           3 2 6 1 0
5           5 3 2 6 1
7           7 5 3 2 6

---

💡 해결 방법

• 캐시는 배열로 관리하며, 가장 최근 사용된 값을 앞쪽에 유지
• 작업이 캐시에 있으면 해당 값을 앞으로 이동
• 캐시에 없으면 가장 오래된 작업(맨 뒤)을 제거하고 새로운 작업을 앞에 삽입

---

💻 코드 구현 (Java)

package partSort;

import java.util.Scanner;

public class Problem4 {
	public int[] solution(int s, int n, int[] arr){
		int[] cache = new int[s];
		for(int x : arr) {
			int idx = -1;
			// 캐시에 이미 있는지 확인
			for(int i = 0; i < s; i++) {
				if(cache[i] == x) {
					idx = i;
					break;
				}
			}
			// 캐시에 없으면: 맨 뒤부터 앞으로 한 칸씩 밀기
			if(idx == -1) {
				for(int i = s - 1; i > 0; i--) {
					cache[i] = cache[i - 1];
				}
			} 
			// 캐시에 있으면: 그 위치부터 앞으로 한 칸씩 밀기
			else {
				for(int i = idx; i > 0; i--) {
					cache[i] = cache[i - 1];
				}
			}
			cache[0] = x; // 새 작업을 가장 앞에
		}
		return cache;
	}

	public static void main(String[] args) {
		Problem4 T = new Problem4();
		Scanner kb = new Scanner(System.in);
		int s = kb.nextInt();
		int n = kb.nextInt();
		int[] arr = new int[n];
		for(int i = 0; i < n; i++) arr[i] = kb.nextInt();
		for(int x : T.solution(s, n, arr)) System.out.print(x + " ");
		kb.close();
	}
}

---

📖 코드 설명

1️⃣ 캐시 내 중복 확인

for(int i = 0; i < s; i++) {
	if(cache[i] == x) {
		idx = i;
		break;
	}
}

• 현재 작업 x가 캐시에 이미 있는지 탐색합니다.
• 있으면 그 위치 idx를 저장, 없으면 -1.

---

2️⃣ 캐시에 없는 경우: 뒤에서 앞으로 한 칸씩 밀기

if(idx == -1) {
	for(int i = s - 1; i > 0; i--) {
		cache[i] = cache[i - 1];
	}
}

• 가장 오래된 값을 제거하고 새 작업을 맨 앞에 삽입

---

3️⃣ 캐시에 있는 경우: 해당 위치부터 앞까지 한 칸씩 밀기

else {
	for(int i = idx; i > 0; i--) {
		cache[i] = cache[i - 1];
	}
}

• 기존 값을 앞으로 이동시키고 해당 자리엔 새 작업을 넣음

---

4️⃣ 새 작업 추가

cache[0] = x;

• 새 작업을 캐시 맨 앞에 삽입합니다.

---

⏳ 시간 복잡도 분석

• 각 작업마다 최대 O(S) 만큼 캐시 이동이 일어납니다.
• 총 작업 수 N → O(N × S)
• 최악의 경우 N=1000, S=10 이므로 O(10,000)

---

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

https://www.inflearn.com/course/자바-알고리즘-문제풀이-코테대비/dashboard

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 강의 | 김태원 - 인프런