문제설명

문제 링크

입력 형식

• 캐시 크기(cacheSize)와 도시이름 배열(cities)을 입력받는다.
• cacheSize는 정수이며, 범위는 0 ≦ cacheSize ≦ 30 이다.
• cities는 도시 이름으로 이뤄진 문자열 배열로, 최대 도시 수는 100,000개이다.
• 각 도시 이름은 공백, 숫자, 특수문자 등이 없는 영문자로 구성되며, 대소문자 구분을 하지 않는다. 도시 이름은 최대 20자로 이루어져 있다.

출력 형식

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

조건

• 캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용한다.
• cache hit일 경우 실행시간은 1이다.
• cache miss일 경우 실행시간은 5이다.

입출력 예제

캐시크기(cacheSize)	도시이름(cities)	실행시간
3	["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"]	50
3	["Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul"]	21
2	["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"]	60
5	["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"]	52
2	["Jeju", "Pangyo", "NewYork", "newyork"]	16
0	["Jeju", "Pangyo", "Seoul", "NewYork", "LA"]	25

요약

즉, LRU 방식에 맞는 자료구조를 생성하고
LRU 방식의 알고리즘으로 캐싱하도록
코드를 구현해야 했다.

---

문제풀이

자료구조 선택

자료구조 선택에 앞서 LRU 캐시 교체 알고리즘에 대해 알고있어야 한다.

캐시 교체 알고리즘

캐시 교체 알고리즘에는 다음과 같은 종류가 있다.

• LRU
• LFU
• FIFO
  FIFO는 알다시피 가장 먼저 들어간 캐시를 교체하는 방식이다.
  생소한 것은 LRU, LFU일텐데

LRU는 가장 오랫동안 사용되지 않은 캐시를 교체하는 방식이다.

출처 : https://hstory0208.tistory.com/entry/%EC%BA%90%EC%8B%9C-%EA%B5%90%EC%B2%B4-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-LRU-LFU?pidx=0

계속 업데이트 되는 FIFO로 생각할 수 있겠다.

그에 맞는 자료구조로 나는 QUEUE를 사용하기로 했다.
FIFO에 성질을 이용하기로 한것이다.

추가로, 캐시저장공간에 이 도시가 있는지 검색하는 것에는 Set 자료구조를 사용하기로 결심했다.

1차시도

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

public class Solution {

    public int solution(int cacheSize, String[] cities) {
        Queue<String> cacheQueue = new LinkedList<>();
        Set<String> cacheSet = new HashSet<>();
        int proceedTime = 0;

        for (String city : cities) {
            city = city.toLowerCase();

            if (!cacheSet.contains(city)) {

                if (cacheSet.size() == cacheSize) {
                    cacheSet.remove(cacheQueue.poll());
                }

                cacheQueue.add(city);
                cacheSet.add(city);
                proceedTime += 4;
            }

            proceedTime += 1;
        }

        return proceedTime;
    }
}

set과 queue에 둘다 업데이트 해주고,
검색에는 set을 사용해주었다.

하지만 실패하는 문제들이 있었고, 생각해보니 캐시 저장공간이 0일 경우에도 캐시에 넣어준다는 알고리즘의 허점이 존재했다.

2차시도

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

public class Solution {

    public int solution(int cacheSize, String[] cities) {
        if(cacheSize==0){
            return cities.length*5;
        }

        Queue<String> cacheQueue = new LinkedList<>();
        Set<String> cacheSet = new HashSet<>();
        int proceedTime = 0;

        for (String city : cities) {
            city = city.toLowerCase();

            if (!cacheSet.contains(city)) {

                if (cacheSet.size() == cacheSize) {
                    cacheSet.remove(cacheQueue.poll());
                }

                cacheSet.add(city);
                proceedTime += 4;
            }

            cacheQueue.remove(city);
            cacheQueue.add(city);
            proceedTime += 1;
        }

        return proceedTime;
    }
}

2차시도에서는 캐시용량이 0일경우 바로 return을 해주는 함수로 만들었다.
그 결과 성공적으로 작동이 되었다.

---

결과

성능 요약

메모리: 117 MB, 시간: 30.01 ms

구분

코딩테스트 연습 > 2018 KAKAO BLIND RECRUITMENT

채점결과

정확성: 100.0
합계: 100.0 / 100.0

제출 일자

2024년 07월 21일 20:43:14

문제 설명

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges