[프로그래머스 17680] 캐시

문제 URL

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

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

 

문제풀이 key point

• 캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용한다
• 캐시 크기가 0인 경우에는 캐시에 보관되는 것이 없으므로 같은 도시가 들어와도 +5초가 되어야 한다

LRU(Least Rcently Used)

• 가장 오랫동안 참조되지 않은 페이지를 교체하는 기법을 말한다
• 캐시 알고리즘 중에서 가장 유명한 알고리즘이다
• 캐시 크기가 3이고 [1, 2, 3] 순으로 호출 되었으며 네번째로 2가 호출되었다고 가정한다
• 2가 캐시에 이미 있는 것을 확인 할 수 있다
• 여기서 중요한 점은 2가 이미 들어있다고 [1, 2, 3]을 유지하는 것이 아니라
• [1, 3, 2] 순으로 변경되게 된다
• 이렇게 변경되는 이유는 캐시에 쌓인지 가장 오래된 1이 가장 오랫동안 참조되지 않았다는 것이고
• 그 다음으로는 3이 들어온 뒤에 가장 오래 호출되지 않았으므로 [1, 3, 2] 순으로 쌓이게 되는 것이다
• 이 점을 유의하고 문제를 풀어보면 해결 될 것이다

 

 

C++ 풀이

#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
 
void mvCache(queue<string>& Q, string str){
    queue<string> tmpQ;
    while(!Q.empty()){
        if(Q.front() != str){
            tmpQ.push(Q.front());
        }
        Q.pop();
    }
    while(!tmpQ.empty()){
        Q.push(tmpQ.front());
        tmpQ.pop();
    }
    Q.push(str);
}
 
//도시명 대문자로 변경
string toUpper(string str){
    for(int i = 0; i < str.size(); i++){
        str[i] = toupper(str[i]);
    }
    return str;
}
 
//캐쉬안에 동일 문자가 있는지 확인
bool strEqual(string str, queue<string> Q){
    int len = Q.size();
    for(int i = 0; i < len; i++){
        if(Q.front() == str){
            return true;
        }
        Q.pop();
    }
    return false;
}
 
int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    
    int len = cities.size();
    queue<string> Queue;
    for(int i = 0; i < len; i++){
        string tmp = toUpper(cities[i]);
        if(Queue.size() < cacheSize){
            //공간이 있는 경우
            
            if(strEqual(tmp, Queue)){
                //동일 문자가 있는 경우
                mvCache(Queue, tmp);
                answer += 1;
            }else{
                //동일 문자가 없는 경우
                Queue.push(tmp);
                answer += 5;
            }
        }else{
            //공간이 없는 경우
            if(strEqual(tmp, Queue)){
                //동일 문자가 있는 경우
                mvCache(Queue, tmp);
                answer += 1;
            }else{
                //동일 문자가 없는 경우
                Queue.push(tmp);
                Queue.pop();
                answer += 5;
            }
        }
    }
    
    return answer;
}

 

Java 풀이

import java.util.LinkedList;
import java.util.Queue;
 
class Solution {
    public int solution(int cacheSize, String[] cities) {
        int answer = 0;
        
        Queue<String> queue = new LinkedList<>();
        
        if(cacheSize == 0) {
            return cities.length * 5;
        }
        
        for(int i = 0; i < cities.length; i++) {
            String str = cities[i].toLowerCase();
            
            if(queue.size() < cacheSize) {
                if(queue.contains(str)) {
                    int len = queue.size();
                    for(int j = 0; j < len; j++) {
                        if(!queue.peek().equals(str)) {
                            queue.offer(queue.peek());
                            queue.poll();
                        } else {
                            queue.poll();
                        }
                    }
                    queue.offer(str);
                    answer += 1;
                } else {
                    queue.offer(str);
                    answer += 5;
                }
            } else {
                if(queue.contains(str)) {
                    int len = queue.size();
                    for(int j = 0; j < len; j++) {
                        if(!queue.peek().equals(str)) {
                            queue.offer(queue.peek());
                            queue.poll();
                        } else {
                            queue.poll();
                        }
                    }
                    queue.offer(str);
                    answer += 1;
                } else {
                    queue.poll();
                    queue.offer(str);
                    answer += 5;
                }
            }
        }
        
        return answer;
    }
}