[프로그래머스 C++] [1차] 캐시

 

[프로그래머스 C++] [1차] 캐시

 

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

프로그래머스

---

 

해결전략

 

cache 캐시

Least Recently Used Algorithm, LRU 알고리즘

대문자 -> 소문자 변환, tolower,  islower

소문자 -> 대문자 변환, toupper,  isupper

---

 

LRU 알고리즘 참고 링크

 

https://dailylifeofdeveloper.tistory.com/355

LRU 알고리즘 (Least Recentely Used) 개념 및 구현방법

 

---

 

코드

 

#include <string>
#include <vector>
using namespace std;

int solution(int cacheSize, vector<string> cities) {
    int time = 0;

    //cacheSize = 0인 경우 예외처리
    if (cacheSize == 0)
        return cities.size() * 5;

    //대문자 -> 소문자 변환
    for (int i = 0; i < cities.size(); i++) {
        for (int j = 0; j < cities[i].size(); j++)
        {
            if (isupper(cities[i][j])) //대문자라면
                cities[i][j] = tolower(cities[i][j]); //대문자를 소문자로 변환
        }
    }
    
    vector<string> LRU(cacheSize);
    
    for (int i = 0; i < cities.size(); i++) 
    {
        int pos = -1;//pos변수 추가. 중복값이 있을때 위치를 알려주는 변수
    
        for (int j = 0; j < cacheSize; j++) { //cache를 순회하며 검색
            if (cities[i] == LRU[j]) //캐시배열(=LRU)에 cities[i]값(=도시이름)이  있다면
                pos = j;
        }

        //cache miss
        if (pos == -1) {
            for (int j = cacheSize - 1; j >= 1; j--) {
                LRU[j] = LRU[j - 1]; //끝부터 1번 위치까지 한칸씩 뒤로 밀어준다.
            }
            time += 5;
        }
        //cache hit
        else{
            for (int j = pos; j >= 1; j--) {
                LRU[j] = LRU[j - 1]; //끝부터 pos위치까지 한칸씩 뒤로 밀어준다.
            }
            time += 1;
        }

        LRU[0] = cities[i]; //0번 위치(=첫 위치)에 cities[i]값을 넣어준다. 
    }

    return time;
}

 

---

 

 

유사문제

 

https://designerd.tistory.com/entry/%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-3250%EB%B2%88#37._Least_Recently_Used(%EC%B9%B4%EC%B9%B4%EC%98%A4_%EC%BA%90%EC%8B%9C_%EB%AC%B8%EC%A0%9C_%EB%B3%80%ED%98%95) 

[코딩테스트] 32~55번: 정렬, 이분탐색, 알고리즘, 스택

37번