[Programmers] [1차]캐시 - 2018 KAKAO BLIND RECRUITMENT

import java.util.LinkedList;
import java.util.Queue;

// [1차]캐시 - 2018 KAKAO BLIND RECRUITMENT
public class Cache { // 캐시 LRU의 이론을 활용하면 어렵지 않은 문제
	public int solution(int cacheSize, String[] cities) {
		int answer = 0;
		Queue<String> cache = new LinkedList<>();

		if (cacheSize == 0) {
			return cities.length * 5;
		}

		for (String ele : cities) {
			ele = ele.toUpperCase();
			if (cache.isEmpty()) {
				cache.offer(ele);
				answer += 5;
			} else if (!cache.isEmpty() && cache.size() <= cacheSize) {
				if (cache.contains(ele)) { // cache hit
					answer++;
					int size = cache.size();
					for (int i = 0; i < size; i++) { // cache hit 시 hit된 원소는 큐의 가장 입구쪽으로 가야함
						if (cache.peek().equals(ele)) {
							cache.poll();
						} else {
							cache.offer(cache.poll());
						}
					}
				} else { // cache miss
					answer += 5;
					if (cache.size() == cacheSize) {
						cache.poll();
					}
				}
				cache.offer(ele);
			}
		}
		return answer;
	}
}

• Queue.contains(Object obj) 로 Cache Hit 판별
• [캐시 교체정책 LRU 이론]
  https://j2wooooo.tistory.com/121
  https://m.blog.naver.com/tlstjd436/221824813403