Level 2 [1차] 캐시 <KAKAO 2018 BLIND RECRUITMENT>

programmers.co.kr/learn/courses/30/lessons/17680?language=python3

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

 

최종 코드

• GitHub github.com/hwayeon351/Programmers-Algorithms

hwayeon351/Programmers-Algorithms

from collections import deque
def solution(cacheSize, cities):
    if cacheSize == 0: return 5*len(cities)
    answer = 0
    cache = deque()
    for city in cities:
        city = city.lower()
        if city not in cache:
            if len(cache) == cacheSize: cache.popleft()
            cache.append(city)
            answer += 5
        else:
            del cache[cache.index(city)]
            cache.append(city)
            answer += 1
    return answer

---

풀이 과정

풀이 시간 46분

from collections import deque
def solution(cacheSize, cities):
	#캐시가 없는 경우는 캐시 히트가 없다
    if cacheSize == 0: return 5*len(cities)
    
    answer = 0
    cache = deque()
    for city in cities:
    	#도시 이름 소문자로 변환
        city = city.lower()
        
        #cache miss인 경우
        if city not in cache:
        	#cache가 꽉 찬 경우, 가장 오랫동안 참조되지 않은 도시 이름을 pop한다
            if len(cache) == cacheSize: cache.popleft()
            #해당 도시 이름을 캐시에 넣는다
            cache.append(city)
            answer += 5
            
        #cache hit인 경우
        else:
        	#해당 도시 이름 캐시에서 지우고, 다시 캐시에 넣어준다
            del cache[cache.index(city)]
            cache.append(city)
            answer += 1
    return answer
#시간복잡도 = O(n), 공간복잡도 = O(n)

---

이전 풀이

풀이 시간  15분

 KAKAO 2018 BLIND RECRUITMENT [1차] 코딩테스트의 3번째 문제이다.(다른 문제 풀이는 아래 참고를 참고하면 된다.)

 문제 조건인 캐시 교체 알고리즘 LRU(Least Recently Used)만 잘 적용하면 쉽게 풀 수 있는 문제다. LRU는 가장 오랫동안 사용되지 않은 페이지를 교체하는 기법이다. 만약, cities = [Jeju, Pangyo, Seoul, Jeju, Pangyo, NewYork], cacheSize = 3일 때, 시간 순서대로 캐시의 상태 변화는 아래 그림과 같다.

 1 ~ 3시간을 살펴보면 캐시에 빈 곳이 있는 상태에서 캐시에 저장되어 있지 않은 단어가 검색되면 최근에 검색된 순으로 캐시에 단어가 쌓이게 된다. 그 다음 4 ~ 5시간처럼 캐시에 있는 단어가 검색되면 Hit가 발생하고, 캐시가 다시 최근에 검색된 순으로 재정렬된다. 캐시가 꽉 차 있는 상태에서 새로운 단어가 검색되면 6시간처럼 새 단어가 캐시에 들어오게 되고 가장 오랫동안 사용되니 않은 Seoul이 캐시에서 지워진다.

 

 이제 LRU의 원리를 알았으니 이를 코드로 적용해보자.

def solution(cacheSize, cities):
    answer = 0
    cache = []
    if cacheSize == 0: return len(cities)*5
    for city in cities:
        city = city.lower()
        if city in cache:
            answer += 1
            cache.pop(cache.index(city))
            cache.append(city)
        else:
            answer += 5
            if len(cache) == cacheSize:
                cache.pop(0)
                cache.append(city)
            else:
                cache.append(city)
    return answer

먼저, cache 리스트를 선언한다. 그 다음 입출력 예제의 5번째처럼 cacheSize = 0이면, cache miss만 일어나므로 그 경우에 바로 cities의 개수 x 5하여 실행 시간을 return한다.

cacheSize가 0이 아니라면 다음 과정을 반복한다. 입력인 cities에 저장되어 있는 도시 이름 순서대로 검색이 되므로 for문을 통해 city를 차례대로 받아온다.

1. city = city.lower()를 하여 모든 문자를 소문자로 나타낸다.(문제에서 대소문자를 구별하지 않는다고 되어 있기 때문이다.)
2. city가 cache에 있다면, cache hit를 의미하므로 answer += 1을 해주고, cache.pop(cache.index(city)) 한 다음, cache.append(city)를 해줌으로써 해당 도시 이름을 cache의 가장 뒤에 위치하도록 한다.
3. city가 cache에 없다면, cache miss를 의미하므로 answer += 5를 해준다. 그 다음 아래 조건을 체크한다.
   1. cache가 꽉 차 있는 경우, cache.pop(0)을 하여 캐시의 0번째 도시 이름을 없애고, cache.append(city)를 해주어 해당 도시 이름을 cache의 가장 뒤에 위치하도록 한다.
   2. cache에 메모리가 남아 있는 경우, cache.append(city)를 하여 해당 도시 이름을 cache의 가장 뒤에 넣어준다.

 

---

참고

• 1. 비밀지도 2021/02/09 - [분류 전체보기] - Level 1 [1차] 비밀지도 Python3

Level 1 [1차] 비밀지도 Python3

• 2. 다트게임 2021/02/09 - [코테 노트/프로그래머스] - Level 1 [1차] 다트게임 Python3

Level 1 [1차] 다트게임 Python3

• 4. 셔틀버스 https://hwayomingdlog.tistory.com/105

Level 3 [1차] 셔틀버스 Python3

• 5. 뉴스 클러스터링

2021/02/09 - [코테 노트/프로그래머스] - Level 2 [1차] 뉴스 클러스터링

Level 2 [1차] 뉴스 클러스터링

• 6. 프랜즈 4블록 2021/02/09 - [코테 노트/프로그래머스] - Level 2 [1차] 프랜즈 4블록

Level 2 [1차] 프랜즈 4블록

• 7. 추석트래픽 https://hwayomingdlog.tistory.com/106

Level 3 [1차] 추석 트래픽 Python3