문제

https://school.programmers.co.kr/learn/courses/30/lessons/17680

---

입력

• 캐시 크기(cacheSize)와 도시이름 배열(cities)을 입력받는다.

---

출력

입력된 도시이름 배열을 순서대로 처리할 때, "총 실행시간"을 출력한다.

---

풀이

제한조건

• cacheSize는 정수이며, 범위는 0 ≦ cacheSize ≦ 30 이다.

• cities는 도시 이름으로 이뤄진 문자열 배열로, 최대 도시 수는 100,000개이다.

• 각 도시 이름은 공백, 숫자, 특수문자 등이 없는 영문자로 구성되며, 대소문자 구분을 하지 않는다. 도시 이름은 최대 20자로 이루어져 있다.

• 캐시의 교체 알고리즘은 LRU를 사용한다.

• cache hit일 경우 실행시간은 1이다.

• cache miss일 경우 실행시간은 5이다.

접근방법

단순 구현

List 또는 Deque를 이용한 단순 구현 문제이다.
가장 오랫동안 사용되지 않은 데이터를 지우는 방식으로 진행한다.

List 또는 Deque를 이용하여, 가장 오랫동안 사용하지 않을 수록 앞쪽으로 배치.
가장 최근에 사용한 것일수록 뒤쪽으로 배치한다.

특정 도시가 주어질때 아래와 같은 확인작업을 거치면 된다.

1. 캐시에 해당 도시가 있는가?
2. 캐시에 해당 도시가 없다면 캐시의 크기가 남았는가?
3. 가장 오래된 도시를 삭제하고 새롭게 추가.

이 문제는 알고리즘을 풀어가는 기술적 요소보다, LRU에 대한 개념적인 지식을 묻는 문제이다.

주의할 점

• 대소문자를 구분하지 않는다.
• 캐시의 사이즈가 0일 수 있다.

---

코드

import java.util.*;

class Solution {
    public int solution(int cacheSize, String[] cities) {
		Deque<String> dq = new ArrayDeque<>();
		int size = 0;
		int answer = 0;
		for (String city : cities) {
            String s = city.toLowerCase();
            
            if(cacheSize == 0){
                answer += 5;
                continue;
            }
            
            // 캐시가 존재한다면, 있는지 확인하자.
            if (dq.contains(s)) {
				dq.remove(s);
				dq.addLast(s);
				answer += 1;
                continue;
			} 
            
            // 캐시에 데이터가 없는 경우
            answer += 5;
            dq.addLast(s);
            if(size < cacheSize){
                size++;
                continue;
            }
            dq.pollFirst();
		}
		return answer;
	}
}