문제 설명

문제를 처음 보고 든 생각: L .... LRU 알고리즘이 뭔데 !!!!!

LRU (Least Recently Used) 알고리즘

LRU 알고리즘은 운영체제에서 나오는 개념으로, 페이지 교체 알고리즘 중 하나이다.

• 페이지 교체 알고리즘 - 페이징 기법으로 메모리를 관리하는 운영체제에서, 페이지 부재가 발생하여 새로운 페이지를 할당하기 위해 현재 할당된 페이지 중 어느 것과 교체할지 결정하는 방법

대표적으로 FIFO, LFU, LRU가 있다.
그 중 LRU는 가장 오랫동안 참조되지 않은 페이지를 교체하는 방식이다.

• Input: 1 - 2 - 3 - 1 - 4 - 5
• Output: 5 - 4 - 1 - 3
  
  
• 4초일 때, 1은 재참조된 것이므로 가장 오랫동안 참조되지 않은 순으로 저장 순서가 변경된다.
• 6초일 때, cache size가 가득차 5가 들어갈 수 없으므로 가장 오랫동안 참조되지 않은 2를 제거한 후 저장한다.

Cache hit, Cache Miss

• Cache hit - CPU가 참조하고자 하는 메모리가 캐시에 존재하는 경우
• Cache Miss - CPU가 참조하고자 하는 메모리가 캐시에 존재하지 않는 경우

입출력 예제

예제 1

cacheSize - 3
cities - ["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"]
실행시간 - 50

실행 시간	0	5	10	15	20	25	30	35	40	45	50
주기억		Jeju	Jeju	Jeju	Pangyo	Seoul	NewYork	LA	Jeju	Pangyo	Seoul
장치			Pangyo	Pangyo	Seoul	NewYork	LA	Jeju	Pangyo	Seoul	Newyork
상태				Seoul	NewYork	LA	Jeju	Pangyo	Seoul	Newyork	LA

예제 2

cacheSize - 3
cities - ["Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul"]
실행시간 - 21

실행 시간	0	5	10	15	16	17	18	19	20	21
주기억		Jeju	Jeju	Jeju	Pangyo	Seoul	Jeju	Pangyo	Seoul	Jeju
장치			Pangyo	Pangyo	Seoul	Jeju	Pangyo	Seoul	Jeju	Pangyo
상태				Seoul	Jeju	Pangyo	Seoul	Jeju	Pangyo	Seoul

---

구현 아이디어

• 가장 오랫동안 참조되지 않은 페이지를 교체 = 가장 앞에 있는 원소를 pop
• 데이터를 저장할 때는 뒤에 원소를 append
  → 자료구조 queue를 사용하여 구현

전체 코드 1 - 틀렸습니다

from collections import deque

def solution(cacheSize, cities):
    answer = 0
    
    # 대소문자 구분을 하지 않기 때문에 모두 소문자로 변환
    for i in range(len(cities)):
        cities[i] = cities[i].lower()
        
    dq = deque()
    
    if cacheSize == 0: # 캐시 크기가 0일 경우
        return len(cities) * 5
    
    for city in cities:
    	# Cache Hit - 1, Cache Miss - 5
        answer += 1 if city in dq else 5
        # 캐시가 가득 찼을 경우 가장 오래된 원소를 제거한 후 저장
        if len(dq) == cacheSize:
            dq.popleft()   
        dq.append(city) 
            
    return answer

전체 코드 2 - 맞았습니다

새로 삽입하는 데이터가 캐시에 있을 경우, 캐시에 있는 데이터를 지워주어야 한다.

from collections import deque

def solution(cacheSize, cities):
    answer = 0
    
    for i in range(len(cities)):
        cities[i] = cities[i].lower()
        
    dq = deque()
    
    if cacheSize == 0:
        return len(cities) * 5
    
    for city in cities:
        if city in dq:
            answer += 1
            dq.remove(city) # 기존 캐시에 들어있던 원소를 제거
        else:
            answer += 5
        if len(dq) == cacheSize:
            dq.popleft()   
        dq.append(city) 
            
    return answer

LRU 알고리즘만 알고 있었다면, 쉽게 풀 수 있는 문제였다.