[Python] 1차 캐시 - 프로그래머스 / 2018 KAKAO BLIND RECRUITMENT

[문제]

https://school.programmers.co.kr/learn/courses/30/lessons/17680

프로그래머스

 

[주요 알고리즘]

• LRU란?  가장 오랫동안 참조되지 않은 페이지를 교체하는 알고리즘. 
• Dictionary의 데이터구조를 사용하여 빠르게 서치한다.
  • 입력 받는 도시의 개수(N)가 100,000개, cachesize(M)는 최대 30으로, O(NM)까지 가능하다.
• 대소문자 구분이 없어야하기 때문에 모든 도시의 이름을 소문자로 변경한다. 

 

[깨달은 점]

• 소문자로 변경하는 함수 a.lower() 
• 다른 풀이를 참고하니 queue를 사용한다. queue 구조를 사용하면 가장 오래된 자료를 곧바로 pop할 수 있다. 대신에 queue에 있는 자료 중 최근에 사용한 자료는 최신화를 시켜줘야하기 때문에 이를 remove하고 다시 append하는 방식으로 구현한다. (참고 : https://eda-ai-lab.tistory.com/503) 

 

[코드] - 37분 소요

def solution(cacheSize, cities):
    answer = 0
    
    dict = {}
    time = 0
    if cacheSize == 0 : 
        return len(cities) * 5
    for city in cities : 
        city = city.lower()
        ## 1씩 증가하고 시작
        for d in dict : 
            dict[d] += 1
        ## city가 dict에 있을 경우
            ## 그 value값을 0으로 변경
            ## time을 +1
        if city in dict : 
            dict[city] = 0 
            answer += 1
        
        ## city가 dict에 없을 경우
            ## len(dict)가 캐시 크기보다 크다면
                ## 가장 value값이 큰 key 삭제하고 새로 생성
            ## 그렇지 않다면 새로 생성
        else : 
            if len(dict) >= cacheSize : 
                max_city = None
                max_num = 0
                for d in dict : 
                    if not max_city :
                        max_city = d
                        max_num = dict[d]
                    if max_num < dict[d]: 
                        max_city = d
                        max_num = dict[d]
                del dict[max_city]
                
                dict[city] = 0
            else : 
                dict[city] = 0
            answer +=5
    return answer