캐시 lv-2

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

프로그래머스

 

#include <string>
#include <vector>
#include <deque>
#include<iostream>
#include <unordered_map>
using namespace std;

int solution(int cacheSize, vector<string> cities) {
    unordered_map<string, string>um;
    int answer = 0;
    deque<string> cache;
    char ch;
    for (int y = 0; y < cities.size(); ++y) {
        for (int x = 0; x < cities[y].size(); ++x) {
            if (cities[y][x] >= 'A' && cities[y][x] <= 'Z') {
                cities[y][x] = 'a' + cities[y][x] - 'A';
            }
        } // 대소문자 구분 없는 조건
        if (y < cacheSize) { //deque를 통해 cacheSize만큼 원소를 넣는다. 
            if (um[cities[y]] == cities[y]) { // 다만, 히트인 경우 해당 원소를 직접 찾아가서 지우고 갱신
                answer += 1;
                int idx = 0;
                for(auto st : cache){
                    if (st == cities[y]) { 
                        cache.erase(cache.begin() + idx);
                        break;
                    }
                    idx++;
                 }
                cache.push_back(cities[y]);
                continue;
            }
            cache.push_back(cities[y]);
            um[cities[y]] = cities[y];
            answer += 5;
        }
    }
    if (cacheSize == 0) { // 캐시사이즈가 0이면 바로 답 추출.
        return answer + cities.size() * 5;
    }

    for (int y = cacheSize; y < cities.size(); ++y)
    {
        //hash map
        if (um[cities[y]] == cities[y]) { // hit
            answer += 1;
            int idx = 0;
            for (auto st : cache) {
                if (st == cities[y]) {
                    cache.erase(cache.begin() + idx);
                    break;
                }
                idx++;
            }
            cache.push_back(cities[y]);
        }
        else { //miss
            if (cache.size() < cacheSize) { // 캐시사이즈
                um[cities[y]] = cities[y];
                cache.push_back(cities[y]);
                answer += 5;
                continue;
            }
            string tmp = cache.front();
            cache.erase(cache.begin());
            um[tmp] = "";
            um[cities[y]] = cities[y];
            cache.push_back(cities[y]);
            answer += 5;
        }
        //hash에 없을 경우 queue pop 및 push  +5
    }

    return answer;
}

int main() {
    cout<<solution(2,{ "a","a","a","b","b","b","c", "C","c"});
}

풀이 설명 ( 못풀었다면 못푼이유 )

해시맵은 해당 원소가 히트인지 여부를 파악하고 히트이면 answer +=1 미스이면 answer+=5 와 더불어 해시 키값을 설정한다.

디큐의 경우는 히트이면 기존 원소의 인덱스를 마지막 인덱스로 갱신하는 용도이다. 디큐의 경우 특정인덱스에 접근 하여 원소를 삭제함과 동시에 push_back을 통해 원소값을 추가하는 특징이 있기에 디큐를 사용했다.

중요한 부분은 캐시사이즈를 고려하는 것이다. 미스 인 경우 그리고 캐시사이즈가 남이있다면 기존 원소들은 그대로 놓고 새로운 값을 추가만하면된다.

• 답지를 직접적으로 참조하기보단, 힌트와 TC를 보면서 풀이했다. 그럼에도 시간 초과.