프로그래머스 캐시 c++

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

프로그래머스

큐, 덱을 사용해 풀어봤다. 그런데 맨 처음에 캐시 사이즈보다 적게 덱에 들어 있을 때 일단 넣어버려서 똑같은 값이 두 번 들어갈 수 있다는 걸 깨달았다 진짜 어이가 없다. 아ㅏㅏㅏㅏㅏㅏㅏㅏ 그리고 문제 이제 보니 캐시 사이즈 30개밖에 안 들어와서 그냥 덱 순회 하고 set 안 만드는 게 낫다.... 바보짓 했다. 문제를 똑바로 보자 진짜.. 그리고 LRU알고리즘이 생소해서 까다로운 문제였다

#include <string> // 실패코드
#include <vector>
#include <unordered_set>
#include <deque>
#include <iostream>
using namespace std;

string    change_to_lower(string s)
{
    string res;
    for (int i = 0; i < s.size(); i++)
        res += tolower(s[i]);
    return res;
}


int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    unordered_set<string> set;
    deque<string>         dq;
    
    for (auto city : cities) // 아주 편하다 오토 idx사용할 상황 아니면 사용,
    { // for (int i = 0; i < 자료구조 사이즈; i++)와 동일하게 작동한다.
        city = change_to_lower(city);
        if (set.size() < cacheSize) // 아직 캐시가 다 안 찼을 때
        {
            set.insert(city);
            dq.push_back(city);
            answer += 5;
            continue ;
        }
        if (set.find(city) == set.end()) // cache miss(city없는거 들어왔을 때)
        {
            set.erase(dq.front());
            set.insert(city); // 새로온놈 추가
            dq.pop_front();
            dq.push_back(city);
            answer += 5;
            continue ;
        }
        if (dq.front() != city) // 중간에 있는거
        {
            deque<string>   buffer;
            while (dq.front() != city)
            {
                buffer.push_back(dq.front());
                dq.pop_front();
            }
            dq.pop_front();
            while (buffer.empty() == 0)
            {
                dq.push_front(buffer.back());
                buffer.pop_back();
            }
            dq.push_back(city);
            answer += 5;
        }
        else // 맨 앞에 있는거
        {
            dq.pop_front();
            dq.push_back(city);
            answer++;
        }
    }
    // for(auto city : set) cout << city << "\n";
    return answer;
}

// 이미 캐시에 있는 값이 들어오면 그대로 두고 cache hit(1초)
// 없는 값이 들어오면 제일 오래된 놈 제거하고 새로온 놈 들어오고 cache miss(5초)

맞게 푼 풀이..

#include <string> // 성공코드
#include <vector>
#include <unordered_set>
#include <deque>
#include <iostream>
using namespace std;

string    change_to_lower(string s)
{
    string res;
    for (int i = 0; i < s.size(); i++)
        res += tolower(s[i]);
    return res;
}


int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    deque<string>         dq;
    
    for (auto city : cities) // 아주 편하다 오토 idx사용할 상황 아니면 사용,
    { // for (int i = 0; i < 자료구조 사이즈; i++)와 동일하게 작동한다.
        city = change_to_lower(city);
        int     i = -1;
        while (++i < dq.size())
            if (dq[i] == city)
                break ;
        if (i != dq.size() && dq.empty() == 0) // dq 안에 city 있음 == 있는 놈이 들어옴
        {
            if (dq.size() >= cacheSize)
                dq.erase(dq.begin() + i);
            answer += 1;
        }
        else // 없는 놈이 들어옴
        {
            if (dq.empty() == 0 && dq.size() >= cacheSize)
                dq.pop_front();
            answer += 5;
        }
        if (cacheSize)
            dq.push_back(city);
        
        // for (int j=0; j<dq.size(); j++)
        //         cout << dq[j] << ", ";
        // cout << endl;
    }
    // for(auto city : set) cout << city << "\n";
    return answer;
}

// 이미 캐시에 있는 값이 들어오면 그대로 두고 cache hit(1초)
// 없는 값이 들어오면 제일 오래된 놈 제거하고 새로온 놈 들어오고 cache miss(5초)

환장 하겠다~~