캐시

코딩테스트 연습 - [1차] 캐시 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - [1차] 캐시

풀이)

접근)

LRU란 캐시 교체 알고리즘인데 캐시미스가 났을 때 사용한지가 가장 오래된 데이터를 교체하는 것이다.

캐시의 크기대로 배열을 생성하고 도시이름들이 담기게 되는데 이 때 순서도 같이 기록해야한다.

1번부터 5번 캐시가 가득 찼을 때 캐시 미스가 난다면 교체를 해야하는데 몇번 캐시의 데이터를 교체해야하는지 파악하기 위해서다. 

캐시가 적중되거나 미스가 나서 교체를 한다면 사용순서를 갱신해준다.

알고리즘)

cities를 탐색하면서 해당 도시를 저장하는 동시에 현재의 진행순서를 캐시배열에 같이 넣어준다.

캐시미스가 난다면 진행순서가 가장 낮은 캐시배열의 데이터를 갱신한다.

캐시가 적중되거나 미스가 날 때 모두 사용순서를 갱신해준다.

코드)

def solution(cacheSize, cities):
    for i,city in enumerate(cities):
        cities[i] = city.upper()
    num = 1
    cache = ["" for i in range(cacheSize)]
    sequence = [0 for i in range(cacheSize)]   # 사용된 순서
    answer = 0
    if cacheSize == 0:
        answer = len(cities) * 5
    else:
        for city in cities:
            
            hit = 0
            hitIndex = -1
            for i in range(cacheSize): # 캐시 히트 확인
                if city == cache[i]:
                    hit = 1
                    hitIndex = i
                    break
            if hit == 1:
                sequence[hitIndex] = num
                num += 1
                answer += 1 
            else:
                minIndex = 0
                for i in range(cacheSize):
                    if sequence[minIndex] > sequence[i]:
                        minIndex = i # 가장 오래전에 사용된 인덱스
                #print(minIndex)
                sequence[minIndex] = num
                cache[minIndex] = city
                num += 1
                answer += 5
            #print(cache)
            #print(sequence,answer)
    return answer