2018 카카오 블라인드 채용 문제입니다.
문제풀이
먼저, LRU 알고리즘 : 새로운 페이지가 등장했을 때, 가장 오래전에 사용된 페이지를 캐시에서 삭제합니다.
즉, 캐시 사이즈가 2이고, 캐시에 t=1일 때 A, t=2일 때 B가 들어오면, A와 B는 캐시가 비어있으므로 그냥 캐시에 추가합니다. t=3 일 때 C가 등장한다면, 가장 오래전에 사용된 A를 캐시에서 제거하고 C를 캐시에 추가합니다.
=> 큐 자료구조를 활용합니다.
1. cities에서 city를 꺼내고 대소문자를 구분하지 않는다고 했으므로 전부 대문자로 변환합니다.
2. queue 자료구조로 cache를 선언합니다. cache의 앞에 있을수록 사용한지 오래된 페이지입니다.
위의 예에서 cache는 [A] -> [A, B] -> [B, C]로 변화합니다.
3-1. city가 cache에 있다면 cache에서 city를 삭제하고 city를 다시 넣어줍니다. answer에는 1을 더해줍니다.
* pop()으로 꺼내지 않고 remove(cache)로 지워야합니다. 여기서 city를 지우는 이유는 city를 가장 최근에 사용된 것으로 바꾸기 위해 cache의 맨 끝에 넣기 위함인데, pop()으로 지우면 cache에서 city가 아니라 가장 오래된 것이 지워집니다.
** cache가 [A, B, C] 일 때, B가 들어오면, cache를 [A, C, B]로 바꾸기 위해 B를 지운 후 다시 넣는 것을 말합니다.
3-2. city가 cache에 없다면 cache의 첫번째 요소를 제거(pop())한 후, city를 cache에 넣어줍니다. answer에는 5를 더해줍니다.
*cache의 크기가 cacheSize보다 작을 때는 첫번째 요소를 제거하지 않고 city를 cache에 넣어주는 작업만 수행합니다.
Python Code
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
from collections import deque
def solution(cacheSize, cities):
if cacheSize == 0 : return len(cities) * 5
answer = 5
cache = deque([cities[0].upper()])
for city in cities[1:]:
c = city.upper()
if c in cache:
answer +=1
cache.remove(c)
cache.append(c)
else:
answer += 5
cache.append(c)
if len(cache) > cacheSize:
cache.popleft()
return answer
|
cs |
Line 4 : cacheSize가 0인 경우에는 cities의 요소 수에 5를 곱해 반환합니다.
Line 6 : cache에 cities의 첫번째 요소를 넣은 채 선언합니다. 따라서 answer 역시 5로 초기화합니다.
Line 9 : city가 cache에 있는 경우입니다.
Line 13 : city가 cache에 없는 경우입니다.
문제 링크
코딩테스트 연습 - [1차] 캐시
3 [Jeju, Pangyo, Seoul, NewYork, LA, Jeju, Pangyo, Seoul, NewYork, LA] 50 3 [Jeju, Pangyo, Seoul, Jeju, Pangyo, Seoul, Jeju, Pangyo, Seoul] 21 2 [Jeju, Pangyo, Seoul, NewYork, LA, SanFrancisco, Seoul, Rome, Paris, Jeju, NewYork, Rome] 60 5 [Jeju, Pangyo, S
programmers.co.kr
'알고리즘 > 프로그래머스' 카테고리의 다른 글
| [프로그래머스] 3진법 뒤집기 - Python (0) | 2021.02.08 |
|---|---|
| 프로그래머스 불량 사용자 (0) | 2020.12.03 |
| 프로그래머스 튜플 (0) | 2020.11.30 |
| 프로그래머스 n진수 게임 (0) | 2020.11.10 |
| 프로그래머스 SQL 동명 동물 수 찾기 (0) | 2020.11.09 |