import java.util.LinkedList;
public class Solution {
// [1차] 캐시
// LRU(Least Recently Used) : 가장 오랫동안 참조되지 않은 페이지를 교체하는 방식
// 캐시가 가득 찼을 때, 가장 오랫동안 참조되지 않은 페이지를 찾아서 없애는 과정이 필요
public static int solution(int cacheSize, String[] cities) {
int answer = 0;
String city = "";
LinkedList<String> cache = new LinkedList<>();
if (cacheSize == 0) {
return cities.length * 5;
}
for (int i = 0; i < cities.length; i++) {
city = cities[i].toLowerCase();
if (cache.remove(city)) { // cache hit
cache.addFirst(city); // 제거 후 다시 추가하여 최신화
answer += 1;
} else { // cache miss
if (cache.size() == cacheSize) {
cache.removeLast(); // 가장 오래된 것 제거
}
cache.addFirst(city);
answer += 5;
}
}
return answer;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int cacheSize = 3;
String[] cities = {"Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul"};
System.out.println(solution(cacheSize, cities));
}
}문제 해결을 위해 사용한 LinkedList에 대해 조금 더 알아보자
public void linkedListTest() {
// add, remove(실패 시 Exception 발생), element
// offer, poll(실패 시 null 리턴), peek
// LinkedList의 경우 add, remove, offer, poll을 (A)로 사용해 (A), (A)First, (A)Last가 가능하다.
// remove의 경우 remove("A")와 같이 지정 삭제가 가능하지만, poll의 경우 poll("A")와 같이 지정 삭제가 불가능하다.
// 1. add & remove & element
LinkedList<String> linkedList1 = new LinkedList<>();
linkedList1.add("A"); // linkedList1.element() => A
linkedList1.add("B"); // linkedList1.element() => A
linkedList1.add("C"); // linkedList1.element() => A
linkedList1.add("D"); // linkedList1.element() => A
System.out.println(linkedList1.element()); // A
linkedList1.remove(); // A
System.out.println(linkedList1.element()); // B
linkedList1.remove("C"); // C
System.out.println(linkedList1.element()); // B
// 2. add, addFirst, addLast & remove, removeFirst, removeLast & element
LinkedList<String> linkedList2 = new LinkedList<>();
linkedList2.add("A"); // linkedList2.element() => A
linkedList2.addFirst("B"); // linkedList2.element() => B
linkedList2.add("C"); // linkedList2.element() => B
linkedList2.addLast("D"); // linkedList2.element() => B
linkedList2.add("E"); // linkedList2.element() => B
System.out.println(linkedList2.element()); // B
linkedList2.removeFirst(); // B
System.out.println(linkedList2.element()); // A
linkedList2.removeLast(); // E
linkedList2.remove("C"); // C
System.out.println(linkedList2.element()); // A
// 3. offer & poll & peek
LinkedList<String> linkedList3 = new LinkedList<>();
linkedList3.offer("A"); // linkedList3.peek() => A
linkedList3.offer("B"); // linkedList3.peek() => A
linkedList3.offer("C"); // linkedList3.peek() => A
linkedList3.offer("D"); // linkedList3.peek() => A
System.out.println(linkedList3.peek()); // A
linkedList3.poll(); // A
System.out.println(linkedList3.peek()); // B
// linkedList3.poll("C"); // 지정 삭제 불가
// 4. offer, offerFirst, offerLast & poll, pollFirst, pollLast & peek
LinkedList<String> linkedList4 = new LinkedList<>();
linkedList4.offer("A"); // linkedList4.peek() => A
linkedList4.offerFirst("B"); // linkedList4.peek() => B
linkedList4.offer("C"); // linkedList4.peek() => B
linkedList4.offerLast("D"); // linkedList4.peek() => B
linkedList4.offer("E"); // linkedList4.peek() => B
System.out.println(linkedList4.peek()); // B
linkedList4.pollFirst(); // B
System.out.println(linkedList4.peek()); // A
linkedList4.pollLast(); // E
// linkedList4.poll("C"); // 지정 삭제 불가
System.out.println(linkedList4.peek()); // A
}
프로그래머스 1차 캐시 문제 풀이 Java
'Java > 프로그래머스' 카테고리의 다른 글
| [Java] 프로그래머스 [Level-2] 주식가격 (0) | 2022.11.28 |
|---|---|
| [Java] 프로그래머스 [Level-3] 여행경로 (0) | 2022.11.28 |
| [Java] 프로그래머스 [Level-3] 자물쇠와 열쇠 (1) | 2022.11.28 |
| [Java] 프로그래머스 [TEST] Uncompress String (0) | 2022.11.28 |
| [Java] 프로그래머스 [TEST] ID Recommendation (0) | 2022.11.28 |
