[ 프로그래머스 / Java ] 1차 캐시

👨‍💻 우선 이 문제를 풀기전에 페이지 교체 알고리즘에 대해 알아보자!

➡️ 운영체제는 주기억장치보다 더 큰 용량의 프로그램을 실행하기 위해 프로그램의 일부만 주기억장치에 적재하여 사용한다. 이를 가상 메모리 기법이라고 한다. 페이징 기법으로 메모리를 관리하는 운영체제에서 필요한 페이지가 주기억장치에 적재되지 않았을 때(페이지부재) 어떤 페이지 프레임을 선택하여 교체할 것인지 결정하는 방법을 페이지 교체 알고리즘이라 한다.

☑️ 프레임 : 물리 메모리를 일정한 크기로 나눈 블록

☑️ 페이지 : 가상 메모리를 일정한 크기로 나눈 블록

---

💡 페이지 교체 알고리즘의 종류

• OPT(Optimal Page Replacement) : 앞으로 가장 오랫동안 사용되지 않을 페이지 교체
• FIFO(First In First Out) : 메모리에 가장 먼저 들어온 페이지를 가장 먼저 제거
• LRU(Least Recently Used) : 가장 오래전에 사용된 페이지를 교체
• LFU(Least Frequently Used) : 사용 빈도(참조 횟수)가 가장 적은 페이지 교체
• MFU(Most Frequently Used) : 사용 빈도(참조 횟수)가 가장 많은 페이지 교체
• NUR(Not Used Recently) : 최근에 사용하지 않은 페이지 교체

---

👨‍💻 문제 이해하기

캐시 저장소 크기에 도시 이름들을 순차적으로 저장한다. 순차적으로 저장하면서 캐시 크기까지 리스트가 차면 비교를 하면서 같으면 페이지 교체 횟수(cache hit)을 ++ 해준다. 다르면 cache miss += 5를 해준다. 여지없이 리스트와 맵을 사용해보자! 

if(cacheSize == 0) {
	return 5 * cities.length;
}
int time = 0;
List<String> cache = new LinkedList<>();

for(String city : cities) {
	city = city.toLowerCase();
    
    if(cache.contains(city)) {
    	cache.remove(city);
        cache.add(city);
        time++;
    } else {
    	if(cache.size() == cacheSize) {
        	cache.remove(0);
        }
        cache.add(city);
        time += 5;
    }
}
return time;

☑️ ArrayList가 아닌 LinkedList를 사용한 이유는 노드 기반의 데이터 구조로, 각 요소가 다음 요소에 대한 참조를 가지고 있기 때문이다. 따라서 삭제할 때는 해당 노드를 찾아 연결만 끊으면 되고 추가는 기존의 마지막 요소만 새 요소를 가리키면 되기 떄문에 O(1) 시간 복잡도를 가진다.

☑️ 위 코드를 실행하면 아래와 같은 결과를 가질 수 있다.

[jeju]
5
[jeju, pangyo]
10
[jeju, pangyo, seoul]
15
[pangyo, seoul, newyork]
20
[seoul, newyork, la]
25
[newyork, la, jeju]
30
[la, jeju, pangyo]
35
[jeju, pangyo, seoul]
40
[pangyo, seoul, newyork]
45
[seoul, newyork, la]
50

---

if(cacheSize == 0) return 5 * cities.length;

LinkedHashMap<String, Integer> cache = new LinkedHashMap<String, Integer>(cacheSize, 0.75f, true) {
	protected boolean removeEldestEntry(Map.Entry<String, Integer> eldest) {
    	return size() > cacheSize;
    }
};

int time = 0;
for(String city : cities) {
	city = city.toLowerCase();
    if(cache.containsKey(city)) {
    	time++;
    } else {
    	time += 5;
    }
    cache.put(city, 1);
    }
return time;

☑️ 0.75f : 로드 팩터(load factor)로 내부적으로 저장소 확장이 필요한 시점을 결정한다. 0.75는 기본값이다.

☑️ true : 접슨 순서(access-older)를 기반으로 요소의 순서를 유지한다는 것이다. (false : 삽입 순서를 유지)

☑️ removeEldestEntry 메서드 오버라이드

• LinkedHashMap 에서 가장 오래된 항목을 제거할지 여부를 결정하는 메서드
• 이 메서드는 맵에 새 항목이 추가될 때마다 호출된다.
• eldest 매개변수는 현재 맵에서 가장 오래된 항목을 나타낸다.

// eldest 매개변수 결과
jeju=1
jeju=1
jeju=1
jeju=1
pangyo=1
seoul=1
newyork=1
la=1
jeju=1
pangyo=1

• return size() > cacheSize 는 맵의 크기가 캐시 크기를 초과하면 가장 오래된 항목을 제거하라는 것을 의미

// return size() > cacheSize 결과
false
false
false
true
true
true
true
true
true
true

➡️ LRU 로직의 핵심

 

//캐시 결과
{jeju=1}
5
{jeju=1, pangyo=1}
10
{jeju=1, pangyo=1, seoul=1}
15
{pangyo=1, seoul=1, newyork=1}
20
{seoul=1, newyork=1, la=1}
25
{newyork=1, la=1, jeju=1}
30
{la=1, jeju=1, pangyo=1}
35
{jeju=1, pangyo=1, seoul=1}
40
{pangyo=1, seoul=1, newyork=1}
45
{seoul=1, newyork=1, la=1}
50

🔥 내일 코테 보러가는데 합격하기를!!