[프로그래머스] - 캐시

문제

 

조건

 

입출력 형식

 

입출력 예제

 

솔루션

1. 링크드 리스트 자료구조를 사용하였다.
   • Why ?) 큐를 사용할까 고민했지만 FIFO 형태이므로, 큐 중간 위치에 있는 데이터를 제거하지 못하기 때문에 큐는 적합하지 않다고 판단하여 링크드 리스트를 채택.
2. 먼저 특이한 상황을 처리한다. 캐시 사이즈가 0 이라면, 캐시에 쌓이는 것이 하나도 없으므로 모두 캐시 미스가 발생한다. 따라서 아래의 반복문을 갈 필요도 없이 총 cities 갯수 x 5를 반환해주면 된다.
3. 캐시 사이즈가 0이 아니라면, cities 갯수만큼 반복문을 수행한다.
   1. 대소문자 구분이 없다고 했으므로, cities[i]를 소문자로 바꾼다. (대문자로 바꿔도 무방)
   2. 먼저 시간을 5만큼 더해준다.
   3. 캐시에 현재 비교하려는 cities[i]가 존재한다면, 캐시에 존재하는 cities[i]를 지우고 맨 마지막에 다시 추가해준뒤 시간을 4만큼 빼준다.
      • 캐시 힛이 되었기 때문에 실행 시간은 5가 아닌 1이므로 4를 빼주는 것.
   4. 캐시에 존재하지 않는다면, 캐시 미스가 일어난 것이므로 캐시에 넣어줘야 하는데, 현재 링크드 리스트 캐시 사이즈가 cacheSize와 동일하다면 (가득찼다면), 캐시의 맨 앞 데이터를 지우고 추가해주면 된다.
4. 결과로 나온 time을 반환한다.

 

Code

• 전체 코드 : https://github.com/SubAkBa/Algorithm_Chung_Son/blob/master/Programmers/Solution_cache.java

 

결과