[프로그래머스, Lv2] [1차] 캐시 (LRU 알고리즘, Java)

문제설명

입력 & 출력

나의 풀이

문제 접근 방법

"프로그래머스 - 1차 캐시" 문제는 캐시 크기를 측정하는 프로그램을 작성하는 것 입니다. 문제에서 나와 있듯이 LRU(Least Recently Used) 알고리즘을 사용하여 풀이하면 됩니다.

 

문제의 핵심은 LRU 알고리즘의 특성인 캐시가 가득 찼을 때 가장 오랫동안 사용되지 않은 항목을 제거하는 방식을 생각하면 어렵지 않게 풀 수 있습니다.

 

물론 순서를 유지하는 LinkedHashMap 같은 자료구조를 사용하면 O(1)로 처리할 수 있으므로 성능이 더 좋아질 수 있지만, ArrayList 자료구조를 사용해서도 충분히 구현할 수 있습니다.

 

[JAVA] ArrayList 알아보기 (동적 배열)

---

 

먼저 ArrayList에는 위와 같은 순서로 도시들이 들어갈 것 입니다.

 

 

캐시 히트와 미스를 알 수 있도록 예제를 변경해서 설명하자면, [제주, 판교, 서울, 뉴욕, 뉴욕]이 도시 배열로 주어질 때 위와 같이 진행이 될 것입니다.

 

처음에 서울을 리스트에 넣을 때 리스트에 서울이 없기 때문에 즉, 캐시에 현재 넣을 도시가 존재하지 않기 때문에 "Cache Miss"가 발생합니다. 그리고 가장 오랫동안 사용되지 않은 제주가 삭제되고, 서울이 캐시에 저장됩니다.

 

그 다음 "뉴욕"일 때도 마찬가지로  "Cache Miss"가 발생하고, 그 다음 뉴욕은 현재 캐시에 있기 때문에 "Cache Hit"가 발생합니다.

 

따라서 2번의 Cache Miss와 1번의 Cache Hit가 발생합니다. 이 때 처음 캐시가 비어져있을 때 "제주"와 "판교"는 그냥 들어가는 것이 아니라 캐시에 존재하지 않으니깐 이때도 "Cache Miss"가 발생합니다.

 

따라서 4번의 Cache Miss와 1번의 Cache Hit를 계산하면 21초가 나오게됩니다.

 

전체 코드

 

도시를 순회하면서 Cache Hit와 Cache Miss를 조건문에 따라서 실행시간을 계산해줍니다.

 

• 10번째 줄
  • 캐시가 비어있을 경우 즉, 캐시가 없을 경우에는 전부 Miss

문제에서  대소문자 구분을 하지 않는다. 라고 했기 때문에 toUpperCase()메서드를 사용하여 대문자로 전부 바꿔줍니다.

 

• 17번째 ~ 28번째 줄(반복문)
  • 캐시 히트가 발생했을 때에는 먼저 해당 도시를 삭제하고, 다시 추가를 해줍니다.
  • 캐시 미스가 발생했을 때에는 캐시가 비어있을 때와 비어있지 않을 때를 분기처리해줍니다.

cache = [A, B, C]  // 초기 상태

cache.remove(0);    // 가장 오래된 A 제거 → [B, C]
cache.add("D");     // 새로 추가된 D → [B, C, D]

• 꽉 차있다면 0번째 요소 즉 가장 오랫동안 사용되지 않은 도시를 삭제해줍니다.