[알고리즘] 프로그래머스 캐시 -2018 KAKAO BLIND RECRUITMENT-

 

 

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

프로그래머스

 

 

캐시 문제를 풀어 봤습니다. ㅎㅎ

이 문제는 교체 알고리즘으로 LRU 를 사용하는 캐시 메모리의 hit 값을 구하는 문제입니다.

LRU 운영체제 시간에 보고 정보처리기사 시험준비때 보고 오랜만에 보네요.

LRU란 Least Recently Used 를 의미하며 캐시 교체알고리즘으로 사용되기도 합니다.

간단하게 설명하자면 캐시는 특정 크기의 메모리를 갖고 있는데 캐시 메모리가 꽉 찼을 때 새로운 값이 들어온다면 영어 해석 그대로 가장 최근에 사용되지 않은 값이 새로들어오는 값과 교체가 되야합니다. 

그러므로 캐시는 최근에 사용한 값을 알고 있어야하고 교체시 마다 갱신해줘야 합니다.

LRU만 이해한다면 쉬운 문제였네요.

 

설명과 코드는 밑과 같습니다.

import java.util.ArrayList;
import java.util.List;

class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();

    }

    public int solution(int cacheSize, String[] cities) {
        List<String> cityList = new ArrayList<>(cacheSize); // 큰 인덱스일 경우 최근에 사용
        int answer = 0;

        for (int i = 0; i < cities.length; i++) {
            //캐시사이즈 0인 경우
            if (cacheSize == 0) {
                answer = 5 * cities.length;
                break;
            }
            String city = cities[i].toUpperCase();
            // 캐시 꽉찬 경우
            if (cityList.size() >= cacheSize) {
                // 이미 캐시에 있는 경우 hit 하고 LRU 우선순위 재조정
                if (cityList.contains(city)) {
                    cityList.remove(city);
                    cityList.add(cityList.size(), city);
                    answer += 1;
                } else {
                    //캐시에 없는 경우 cache miss 하고 LRU 우선순위 변경
                    cityList.remove(0);
                    cityList.add(cityList.size(), city);
                    answer += 5;
                }
            } else { //캐시 아직 비어있는 경우
                if (cityList.contains(city)) { // hiy
                    cityList.remove(city);
                    cityList.add(cityList.size(), city);
                    answer += 1;
                } else { //miss
                    cityList.add(cityList.size(), city);
                    answer += 5;
                }
            }
        }
        return answer;
    }
}

 

 

이제 BFS, DFS, DP, 백트랙킹 다시 공부해야겠습니다... 귀차니즘 탈출해야겠씀다

댓글과 공감은 큰 힘이 됩니다. 감사합니다!