자바 알고리즘 문제 풀이 입문. ch06. Sorting and Searching(정렬, 이분검색과 결정알고리즘) : Least Recently Used

 

https://hyejin.tistory.com/1242

자바 알고리즘 문제 풀이 입문. ch06. Sorting and Searching(정렬, 이분검색과 결정알고리즘) : 삽입 정

-> 이전 문제 풀이 

 

4. Least Recently Used

설명

캐시메모리는 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

 

힌트

 

 

문제 풀이 1

public ArrayList<Integer> solution(int s, int n, int[] arr)
{
   ArrayList<Integer> answer = new ArrayList<>();
   for (int i = 0; i < s-1; i++)
   {
      answer.add(0);
   }
   
   for (int i : arr)
   {
      if (answer.size() < s) {
         if (!answer.contains(i)) {
            answer.add(0,i);
         }else
         {
            answer.remove(Integer.valueOf(i));
            answer.add(0, i);
         }
      }else
      {
         if (answer.contains(i)) {
            answer.remove(Integer.valueOf(i));
            answer.add(0, i);
         }else
         {
            answer.remove(s-1);
            answer.add(0, i);
         }
      }
   }
   
   return answer;
}

 

👩‍💻 : 나는 이 문제를 풀 때 Arraylist를 이용해서 풀었는데... ㅎ 강사님이 그렇게 풀지 말라고 하셨다 하핳 

이전에 삽입 정렬에 대해서 배웠으니 삽입 정렬을 이용하라고..! 

 

우선 이것도 정답은 정답이었으니.. 나의 풀이에 대해서 설명해보려고 한다. 

ArrayList<Integer> answer = new ArrayList<>();
for (int i = 0; i < s-1; i++)
{
   answer.add(0);
}

-> Arraylist를 생성하고, 주어진 크기 s -1 전까지 반복문 돌면서 answer에 0 값을 넣어줬다. 

 

if (answer.size() < s) {
   if (!answer.contains(i)) {
      answer.add(0,i);
   }else
   {
      answer.remove(Integer.valueOf(i));
      answer.add(0, i);
   }
}

-> 그 다음 주어진 배열 arr을 반복문 도는데, 이때 answer에  sizer가 주어진 크기 s보다 작으면서 i가 포함되지 않는다면 answer에 add할 때 인덱스 위치를 0으로 지정해서 i 값을 넣어줬다. 그리고 i가  포함된다면 answer  리스트에서 해당 값을 remove 해줬고, 그 다음 다시 answer 리스트에 인덱스 위치는 0으로 지정해서 i 값을 add했다. 

 

else
{
   if (answer.contains(i)) {
      answer.remove(Integer.valueOf(i));
      answer.add(0, i);
   }else
   {
      answer.remove(s-1);
      answer.add(0, i);
   }
}

-> 그리고 만약 answer의 크기가 s보다 클 경우에는 메모리가 꽉 찼다는 의미이므로 i 가 answer 리스트에 이미 있는 값이라면 앞에서 했던 것과 동일하게 answer에 그 값을 제거하고 다시 인덱스의 위치가 0 에 i 값을 add 했다. 

 

그리고 만약 answer에 포함되지 않은 값이라면 answer에 s-1 인덱스의 값을 remove 해주고, 그 다음 인덱스 위치 0에 i 값을 넣어주면 된다. 

 

하긴.. 이 문제 풀면서도 이걸 왜 이 섹션 6에다 넣었지..? 하면서  풀었는데 ..ㅎㅎ 역시나 Arraylist로 풀도록 낸 문제가 아니었다ㅜ 

 

 

문제 풀이 2

public int[] solution2(int size, int n, int[] arr)
{
   int[] cache = new int[size];
   for (int x : arr)
   {
      int pos = -1; // 인덱스 번호 (위치)
      for (int i = 0; i< size; i++)
      {
         if (x == cache[i]) { // hit !
            pos = i;
         }
      }
      if (pos == -1) { // miss 상황
         for (int i = size-1; i >= 1; i--)
         {
            cache[i] = cache[i - 1];
         }
      }else // hit 처리
      {
         for (int i = pos; i >= 1; i--)
         {
            cache[i] = cache[i - 1];
         }
      }
      cache[0] = x;
   }
   
   
   return cache;
}

👾 : 강사님은 이 문제를 Arraylist가 아니라 배열로 만들어서 풀라고 하셨기 때문에 cache라는 크기가 주어진 size 인 int 배열을 만들었다. 

 

그 다음 주어진 배열 arr를 반복문으로 도는데 이때 pos 라는 변수 하나를 만들고 이 변수는 hit 된 인덱스의 위치를 저장할 변수이다. 먼저 cache 배열에 x 값을 가지고 있는지 확인해야 하기 때문에 for문을 돌면서 x == cache[i] 이면 메모리에 x 값이 있다는 의미이므로 pos에 i 값을 저장했다. 

 

반복문을 다 돌고 나서 만약 pos가 -1이라는 건 hit된 값이 없다는 것이므로 배열에 넣어야 하는데 

이때 넣을 때는 옆으로(오른쪽으로) 값을 밀면서 나아가야 하기 때문에 

if (pos == -1) { // miss 상황
   for (int i = size-1; i >= 1; i--)
   {
      cache[i] = cache[i - 1];
   }
}

for문을 돌 때 i가 size-1 부터 1까지만 돌면서 cache[i]에 값을 cache[i-1] 값으로 바꿔준다. 

 

else // hit 처리
{
   for (int i = pos; i >= 1; i--)
   {
      cache[i] = cache[i - 1];
   }
}

또는 pos가 -1이 아니라는 건 hit됐다는 것이므로 for문 반복문을 hit된 위치 pos 부터 1까지만 돌면서 값을 밀어준다. 

 

cache[0] = x;

반복을 마치고는 cache[0]에 x 값을 넣어주면 된다. (최신 값)