Algorithm/Algorithm Test

[프로그래머스] [1차] 캐시 (Java)

MarrRang 2021. 5. 30. 11:34

카테고리

로직 짜기

나만의 카테고리

상식 문제

문제 링크

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

 

코딩테스트 연습 - [1차] 캐시

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", "Ro

programmers.co.kr

요점

  • 캐시와 캐시 교체 알고리즘에 대해 이해해야한다.

참고 지식

  • 캐시 메모리

풀이 (Java)

import java.util.*;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        if (cacheSize == 0) {
            return cities.length * 5;
        }
        
        int answer = 0;
        List<String> cityList = new ArrayList<>();
        for (String city : cities) {
            city = city.toLowerCase();
            
            if (cityList.contains(city)) {
                cityList.remove(city);
                cityList.add(city);
                
                answer += 1;
            } else {
                if (cityList.size() == cacheSize) {
                    cityList.remove(0);
                }
                
                cityList.add(city);
                
                answer += 5;
            }
        }        
        
        return answer;
    }
}

 

캐시에 대해서 알고 있고 LRU(Least Recently Used) 방식을 알고 있다면 풀이 자체는 굉장히 쉬운 문제입니다.

이참에 LRU 말고도 다른 캐시 교체 알고리즘, 페이지 교체 알고리즘에 대해 알아보는것도 좋을것 같습니다.

  • FIFO(First In First Out)
  • LRU(Least Recently Used)
  • LFU(Least Frequently Used)
  • NRU(Not Recently Used)

알고리즘 초보가 정리한 글입니다

더 좋은 방법이나 코드에 대한 코멘트 언제나 환영합니다!

 

 

반응형