[프로그래머스][카카오] 캐시

문제

캐시 크기와 도시이름 배열이 주어질 때 캐시 크기에 따른 실행시간 측정 프로그램을 작성하시오.

문제 출처: 프로그래머스(https://programmers.co.kr/learn/courses/30/lessons/17680)

풀이

캐시 교체 알고리즘인 LRU를 적용시키는 문제였습니다. 처음에 든 고민은 어느 자료구조를 통해서 캐시를 구현해야하나였는데 랜덤 액세스가 가능해야하고(가장 마지막 사용된 부분이 어디인지 모르기 때문에) 삽입, 삭제가 빈번하지 않고 캐시의 값만 바꿔주면 되므로 vector를 사용했습니다.(가장 오래 사용한 것을 빼야하니까 우선순위큐가 생각이 났었지만 랜덤액세스가 불가능하기때문에 안됩니다.) 처음에는 살짝 막막했었는데 우선 캐시사이즈가 가득 차기 전까지는 해당 값이 벡터에 없을 경우엔 무조건 추가를 해주었습니다.(이때에도 miss 이므로 5초가 소요됩니다.) 캐시사이즈가 가득 차고나서는 어떠한 값이 들어왔을 때 vector안에 해당 값이 있는지를 찾음과 동시에 가장 오래 액세스한 자리를 찾습니다. 저는 use라는 배열을 두어서 각 vector의 인덱스의 값이 바뀔 때마다 몇번째 입력값(실제 인풋)이 업데이트 된 것인지를 저장했습니다. 가장 오래 액세스한 자리를 업데이트해주고 use의 값도 업데이트해주며 모든 입력값에 대해 반복하면됩니다. 생각보다 쉬운 문제였습니다! 그런데 코드 채점하자마자 틀려서 왜인가 했더니 문제 조건에서 대소문자를 구별한다는 것을 체크 안해주어서 그런것이었고 간단하게 transform함수를 통해 전부 소문자로 바꾸어서 수행할 수 있도록 했습니다.

(해설: http://tech.kakao.com/2017/09/27/kakao-blind-recruitment-round-1/)

코드

https://github.com/kswim/Algorithm/blob/master/etc/17680.cpp