Lv.2 : [1차] 캐시

👉 문제링크

프로그래머스

---

---

🔸 문제 분석 🔸

• 캐시 교체 알고리즘 중 LRU (Least Recently Used)를 구현하는 문제이다.

🔸 문제 풀이 🔸

• 크기 제한이 있는 큐 형태에서 가장 사용한지 오래 된 도시 이름을 먼저 지워주는 방식으로 구현한다.
• cache hit일 경우는 해당 도시 이름을 가장 최근에 사용한 것으로 옮겨주어야 한다.
• 도시 이름이 대소문자를 구분하지 않아야 하고, cacheSize가 0이 될 수 있음에 유의한다.

---

🔸 코드 🔸

import java.util.ArrayDeque;
import java.util.Queue;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        Queue<String> que = new ArrayDeque<>();

		int answer = 0;

		for (String city : cities) {

			city = city.toLowerCase();

			if (que.contains(city)) {
				que.remove(city);
				que.add(city);
				answer += 1;
			} else {
				answer += 5;

				que.add(city);
				if (que.size() > cacheSize)
					que.poll();
			}
		}

		return answer;
    }
}

🔸 코드 해석 🔸

• 큐에 포함되어 있으면 answer에 +1, 없다면 +5 를 계산한다.
  • 포함되어 있을때 큐에서 해당원소를 지우고 다시 추가하는 방식으로 가장 최근 사용으로 순서를 변경한다.
  • 원소가 없을 시에는 큐에 추가하고, 큐 사이즈가 제한 크기를 넘었을때는 가장 앞 원소를 제거한다.

---

🔸 end 🔸

• 큐를 이용해서 단순히 구현했지만 contains()에서 선형탐색이 이뤄지므로 그닥 효율적인 코드는 아닌 것 같다.
  • HashMap에서 순서를 유지하는 법을 몰랐는데, 다른 사람의 풀이를 보니 LinkedHashMap을 사용해서 구현한걸 보고 새로 알아보게 되었다.
  • LinkedHashMap은 순서를 보장하는 HashMap인데, 기본적인 사용법은 똑같고 링크드 리스트를 적용해서 순서를 보장하는 것 같다. 가장 오래된 원소는 head이고, 최근 원소는 tail에 저장된다.
  • 특별한 기능으로는 removeEldestEntry() 메서드로 조건을 통해 head를 제거할 수 있다.
    • 여기서는 size가 cacheSize가 되면 ture를 반환하도록 작성하면 된다.
• 대소문자를 구분하지 않는다는 조건에서 한 번, 최근 사용한 원소를 앞으로 당겨줘야하는 부분에서 한 번씩 틀렸다.
  • 문제 조건을 더 꼼꼼히보고 분석해야할 필요를 느꼈다.
• 오랜만에 코테를 다시 풀기 시작하는데 좋은 재활치료(?)가 된 문제이다. 새롭게 알게된 개념도 큰 도움이 될 것 같다.