lango

찍먹? 부먹?
난 부먹 개발자.

3 minute read



입출력 예시

Input-1
cacheSize=3, cities=[“Jeju”, “Pangyo”, “Seoul”, “NewYork”, “LA”, “Jeju”, “Pangyo”, “Seoul”, “NewYork”, “LA”]
Output-1
50

Input-2
cacheSize=3, cities=[“Jeju”, “Pangyo”, “Seoul”, “Jeju”, “Pangyo”, “Seoul”, “Jeju”, “Pangyo”, “Seoul”]
Output-2
21

Input-3
cacheSize=0, cities=[“Jeju”, “Pangyo”, “Seoul”, “NewYork”, “LA”]
Output-3
25


문제 풀이

문제를 풀기에 앞서 캐시와 캐시 교체 정책에 대해서 알아보자.

캐시란?
캐시는 데이터나 값을 미리 복사해 놓는 임시 장소이다. 캐시에 데이터를 미리 복사해 놓으면, 계산이나 접근 시간 없이 더 빠른 속도로 데이터에 접근할 수 있다.

캐시 교체 정책
캐시에 모든 데이터를 다 담아둘 수 없기에, 캐시크기는 제한되고 새로운 캐시로 변경되어야 하는데,
캐시 교체 정책을 통해 어떤 데이터를 삭제하고, 새로운 데이터를 캐시로 저장할지를 캐시 교체 정책 알고리즘을 통해 결정할 수 있다.

캐시 교체 정책 알고리즘의 종류

  1. FIFO(First in First Out)
    • 가장 먼저 들어간 캐시를 교체한다.
  2. LFU(Least Frequently Used)
    • 사용 횟수가 가장 적은 캐시를 교체한다.
  3. LRU(Least Recently Used)
    • 가장 오랫동안 사용되지 않은 것 교체한다.

이 문제에서는 캐시 교체 정책중 LRU 알고리즘을 활용하여 문제를 풀어야 한다.

LRU(Least Recently Used)

캐시 공간이 부족할 때, 가장 오랫동안 사용하지 않은 데이터를 제거하고, 새로운 캐시를 부여하는 형식으로 동작한다.

예를 들어 캐시 공간이 3이라고 할 때, 1,2,3,2 순으로 데이터가 들어온다고 하자.
1,2,3 까지는 캐시가 등록이 되는데, 마지막 2가 들어올 때, 2를 사용한 기록이 있기에 2를 최근 캐시로 등록하면 된다. (cache=[1,3,2])

1
2
3
4
5
6

1. cache size=3, 1 -> 2 -> 3 순차 호출
    [tail] 1-2-3 [head]
2. 2 캐시 등록: 2를 head로 이동.
    [tail] 1-3-2 [head]
3. 4 캐시 등록: LRU는 1이므로 1 제거.
    [tail] 3-2-4 [head]


아이디어 도출

캐시와 캐시 교체 정책중 하나인 LRU에 대해서 알았으니, 문제를 풀어보자.
문제 요구사을 살펴보고 생각해낸 아이디어는 다음과 같다.

  • cache hit일 경우는 최근 캐시에 요청한 데이터가 존재할 경우이고 cache miss는 최근 캐시에 요청한 데이터가 존재하지 않을 경우이다.
    • cache hit일 때는 1, cache miss일 때는 5씩을 증가시키면 된다.
  • cache size가 0일 때는 어떤 데이터가 들어와도 5의 실행시간이 걸린다.
  • cache의 공간이 차면 LRU 대로 가장 오래된 tail 요소부터 제거하고 새로운 데이터를 저장한다.


이제 코드를 작성해보자.

1

Queue<String> qu = new LinkedList<>();

먼저 캐시로 사용할 Queue를 LinkedList로 초기화한다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

for(int i=0; i<cities.length; i++) {
    String city = cities[i].toLowerCase();
    if(cacheSize==0) {
        answer+=5;
    }
    else {
        if(qu.contains(city)) {
            answer+=1;
            qu.remove(city);
            qu.offer(city);
        }
        else {
            answer+=5;
            if(qu.size() == cacheSize) {
                qu.poll();
                qu.offer(city);
            }
            else {
                qu.offer(city);
            }
        }
    }
}

캐시 사이즈가 0이라면, cities에 어떤 데이터가 있더라도 데이터마다 5의 실행시간이 걸리기 때문에 가장 바깥 조건문으로 작성하였다.
그리고 최근 캐시에 존재하는 데이터가 들어오면 해당 데이터를 head로 옮기고, 처음 들어오는 데이터라면 head에 바로 등록한다.
이 때, 캐시의 공간이 부족하다면 tail을 제거하고 새로운 데이터를 head에 추가한다.



작성 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

import java.util.*;

class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int size = sc.nextInt();
        String[] cities = {"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"};
        // String[] cities = {"Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul"};
        // String[] cities = {"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"};
        // String[] cities = {"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"};
        // String[] cities = {"Jeju", "Pangyo", "NewYork", "newyork"};
        // String[] cities = {"Jeju", "Pangyo", "Seoul", "NewYork", "LA"};
        // String[] cities = {"1","2","3","2"};
        // String[] cities = {"1","1"};

        long start = System.currentTimeMillis();
        solution(size, cities);
        long end = System.currentTimeMillis();
        System.out.println("\n수행시간 = " + (end-start));
    }
    public static int solution(int cacheSize, String[] cities) {
        int answer = 0;
        Queue<String> qu = new LinkedList<>();
        
        for(int i=0; i<cities.length; i++) {
            String city = cities[i].toLowerCase();
            if(cacheSize==0) {
                answer+=5;
            }
            else {
                if(qu.contains(city)) {
                    answer+=1;
                    qu.remove(city);
                    qu.offer(city);
                }
                else {
                    answer+=5;
                    if(qu.size() == cacheSize) {
                        qu.poll();
                        qu.offer(city);
                    }
                    else {
                        qu.offer(city);
                    }
                }
            }
        }
        return answer;
    }
}

회고

  • 캐시에 대해서 공부하며, 캐시 동작 원리, 캐시 교체 정책에 대해서 알 수 있었다.
  • Queue(큐)를 통해 LinkedList를 활용하여 캐시를 구현할 수 있었다.

You may also enjoy