끄적끄적

문제풀이

1. 딕셔너리 자료구조를 활용하여 생성자의 개수를 세어줍니다. 딕셔너리 dic의 key는 생성자가 되고, value는 생성자의 개수가 됩니다.

2. 1부터 10000까지의 숫자 n의 d(n)을 구하여, 위의 딕셔너리에서 key d(n)의 value에 1을 더해줍니다.

3. 1부터 10000까지의 숫자들을 key로 하여, value가 0인 값을 출력합니다.

Python Code

문제링크

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 

Line 4 : cacheSize가 0인 경우에는 cities의 요소 수에 5를 곱해 반환합니다.

Line 6 : cache에 cities의 첫번째 요소를 넣은 채 선언합니다. 따라서 answer 역시 5로 초기화합니다.

Line 9 : city가 cache에 있는 경우입니다.

Line 13 : city가 cache에 없는 경우입니다.

문제 링크