코딩테스트/기타
[정렬] Least Recently Used .java
머밍
2024. 11. 9. 21:18
설명
캐시메모리는 CPU와 주기억장치(DRAM) 사이의 고속의 임시 메모리로서 CPU가 처리할 작업을 저장해 놓았다가
필요할 바로 사용해서 처리속도를 높이는 장치이다. 워낙 비싸고 용량이 적어 효율적으로 사용해야 한다.
철수의 컴퓨터는 캐시메모리 사용 규칙이 LRU 알고리즘을 따른다.
LRU 알고리즘은 Least Recently Used 의 약자로 직역하자면 가장 최근에 사용되지 않은 것 정도의 의미를 가지고 있습니다.
캐시에서 작업을 제거할 때 가장 오랫동안 사용하지 않은 것을 제거하겠다는 알고리즘입니다.
캐시의 크기가 주어지고, 캐시가 비어있는 상태에서 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
힌트
내 풀이 - 배열
- 모든 작업은 0번 인덱스에 삽입 된다 => 0번 인덱스에 넣기 전에 하나씩 오른쪽으로 밀어야함
- 삽입 전 작업 번호가 이미 캐시에 있다면 그 위치를 기억한다 -> for문
- 새로운 작업을 캐시에 넣으려면 캐시 크기 (s) -1 인덱스 부터~ 1까지 접근하며 오른쪽으로 민다 => j번째에 j-1 값을 넣기
- 이미 있는 작업이면 index 변수로 위치를 기억 => index부터 ~ 1까지 접근하며 오른쪽으로 민다
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int s= sc.nextInt();
int n = sc.nextInt();
int[] arr = new int[s];
for(int i = 0; i < n; i++){
int cnt = sc.nextInt();//입력받은 작업 번호
int index = -1;//삽입할 위치
for(int j = 0; j < s; j++){//캐시 순회
if(arr[j] == cnt){//캐시에 있는 작업
index = j;//위치 기억
break;
}
}
if (index == -1) {//발견 못함
for(int j = s-1; j > 0; j--){
//0번인덱스에 삽입하기 위해 오른쪽으로 하나씩 밀기
arr[j] = arr[j-1];
}
} else {//발견했다면
//인덱스부터 0번까지 오른쪽으로 하나씩 밀기
for(int j = index; j > 0; j--){
arr[j] = arr[j-1];
}
}
//모든 작업은 0번 인덱스로 삽입
arr[0]=cnt;
}
for(int c : arr){
System.out.print(c+" ");
}
}
}내 풀이 - ArrayList
1. remove(), add()
- 작업이 캐시에 없다면 마지막 인덱스의 작업을 remove로 지우기
- 작업이 이미 존재하면 indexOf로 찾은 작업의 번호를 통해 지우기
- 맨 처음 인덱스에 입력받은 작업 넣기
import java.util.ArrayList;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int s = sc.nextInt();
int n = sc.nextInt();
ArrayList<Integer> cache = new ArrayList<>();
for(int i = 0; i < s; i++) {
cache.add(0);//초기화
}
for(int i = 0; i < n; i++) {
int cnt = sc.nextInt();
int index = cache.indexOf(cnt);//캐시에 있는지 확인
if(index == -1) {
cache.remove(s-1);//마지막 작업 제거
} else {
cache.remove(index);
}
cache.add(0,cnt);//맨 처음에 현재 작업 넣기
}
for(int c : cache) {
System.out.print(c + " ");
}
}
}
2. set(인덱스, 교체할 값)
인덱스에 교체할 값을 넣는다
package test;
import java.util.ArrayList;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int s = sc.nextInt();
int n = sc.nextInt();
ArrayList<Integer> cache = new ArrayList<>();
for(int i = 0; i < s; i++) {
cache.add(0);//초기화
}
for(int i = 0; i < n; i++) {
int cnt = sc.nextInt();
int index = cache.indexOf(cnt);//캐시에 있는지 확인
if(index == -1) {
for(int j = s-1; j > 0; j--) {
cache.set(j, cache.get(j-1));//j자리에 이전 값을 넣기
}
} else {
for(int j = index; j > 0; j--) {
cache.set(j,cache.get(j-1));
}
}
cache.set(0,cnt);//맨 처음에 현재 작업 넣기
}
for(int c : cache) {
System.out.print(c + " ");
}
}
}
다른 풀이
배열로 푼 내 풀이를 함수형으로 구현했다
import java.util.Scanner;
public class Main {
public int[] solution(int s, int n, int[] arr) {
int[] cache = new int[s];
for(int x : arr) {
int pos = -1;//위치
for(int i = 0; i < s; i++) {
if(x==cache[i]) pos = i;//찾으면 인덱스 저장
}
if(pos == -1) {
for(int i = s-1; i >=1; i--) cache[i] = cache[i-1];
} else {
for(int i = pos; i>=1; i--) cache[i] = cache[i-1];
}
cache[0] = x;
}
return cache;
}
public static void main(String[] args) {
Main T = new Main();
Scanner sc = new Scanner(System.in);
int s = sc.nextInt();
int n = sc.nextInt();
int[] arr = new int[n];
for(int i = 0; i < n; i++) arr[i] = sc.nextInt();
for(int x : T.solution(s,n,arr)) System.out.print(x + " ");
}
}
💡💡
오른쪽이나 왼쪽으로 미는 문제들이 많이 나오는데 배열을 통해 직접 구현하면서 쉽게 익힐 수 있었다
물론 리스트의 메서드를 사용하면 편하지만 배열로도 구현할 줄 알아야 한다