[programmers] [1차] 캐시 - 2018 KAKAO BLIND RECRUITMENT

<[1차] 캐시>

문제(출처: https://school.programmers.co.kr/learn/courses/30/lessons/17680)

 

 

문제 풀이

   - my solution

 

def solution(cacheSize, cities):
    answer = 0
    
    result=[]
    
    for i in range(len(cities)):
        cities[i]=cities[i].lower() #대문자, 소문자 상관 x
        if(cacheSize==0): #cacheSize가 0이면 다 실행 시간 5
            answer=len(cities)*5
            break
        if(cities[i] in result): #값이 있으면
            result.pop(result.index(cities[i]))
            result.append(cities[i]) #맨 끝으로 
            answer+=1 # 1
        else:
            if(len(result)==cacheSize): #캐시 크기만큼 다 채워져있으면
                result.pop(0) #제일 안쓰는 것 pop
            answer+=5 #5
            result.append(cities[i])

    return answer

  이 문제에서 캐시 교체 알고리즘으로 LRU(Least Recently Used)를 사용한다. 

  LRU 알고리즘에 대해 간단하게 말하자면 제일 오랫동안 참조되지 않은 데이터를 제거하는 방식이라고 할 수 있다.

 

  처음에는 이 문제를 dict를 사용하여 해결하려 했지만 코드를 구현하다 보니 단순 list로 가능할 것 같아 

  다시 처음부터 코드를 구현하였다.

 

  1) cities list 순회

     1-1) 대문자, 소문자 상관이 없으므로 소문자로 다 바꿔서 저장

     1-2) cacheSize가 0이면 저장할 곳이 없어 다 miss이므로 cities의 길이만큼 5를 곱한 후 종료

     1-3) list 안에 값이 있다면 이미 한번 쓴 적이 있어 캐시 안에 있다는 뜻

             -> 최근에 사용했다는 것을 나타내기 위해 리스트의 맨 뒤로 보냄

             -> hit 이므로 실행시간 1 추가

     1-4) list 안에 값이 없는 경우

            1-4-1) 캐시 크기만큼 캐시가 다 차있으면 -> 제일 안 쓰는 것은 맨 앞을 의미하므로 맨 앞 값 pop

            1-4-2) miss를 나타내므로 실행시간 5 추가

            1-4-3) 캐시에 저장

---

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges