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

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/17680

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

 

풀이

처음에 문제를 풀 때는 map을 활용하여 문제를 풀었다. 풀고 보니 너무 복잡하게 푼 것 같아서 다른 사람의 코드를 찾아서 더 좋게 고쳐보았다.

#include <string>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    map <string, int> cache;
    vector <pair <int, string>> tmp;  // map이 value기준으로 정렬이 안되므로 vector도 선언해줌
    
    if(cacheSize == 0) return cities.size()*5;
    
    for(int i = 0; i < cities.size(); i++){
        transform(cities[i].begin(), cities[i].end(), cities[i].begin(), ::toupper);
        if(cache[cities[i]] == 0){
            if(tmp.size() < cacheSize) tmp.push_back(make_pair(i+1, cities[i]));
            else{
                sort(tmp.begin(), tmp.end());
                cache[tmp[0].second] = 0;
                tmp[0].second = cities[i];
                tmp[0].first = i+1;
            }
            cache[cities[i]] = i+1;
            answer += 5;
        }
        else{
            for(int j = 0; j < cacheSize; j++){
                if(tmp[j].second == cities[i]){
                    tmp[j].first = i+1;
                    break;
                }
            }
            cache[cities[i]] = i+1;
            answer++;
        }
    }

    return answer;
}

이런 식으로 map으로 cache를 구성하고 map은 value를 기준으로 한 정렬이 되지 않으므로 vector 자료형을 pair로 선언해줘서 정렬 후 사용해 주었다. 문제는 맞았지만 간단한 문제를 너무 복잡하게 푼 것 같아서 다른 풀이를 찾아보았고, 밑에 두 개의 블로그를 보고 힌트를 얻어 다시 풀어보았다.

 

 

https://algosu.tistory.com/80

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

https://jayrightthere.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%BA%90%EC%8B%9C

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

 

첫 번째 블로그에서는 deque라는 자료구조 힌트를 얻었고, 구현은 거의 두 번째 블로그에서 힌트를 얻었다.

deque를 활용하여 앞에 있는 데이터일수록 오래된 데이터이고 뒤에 있을수록 최신 데이터로 정하고 구현해주었다.

 

if(cacheSize == 0) return 5 * cities.size();
deque <string> cache;

먼저 cacheSize가 0일 수도 있으니 0일 때는 바로 계산해서 return 해주었다. 그러고 cache를 위한 deque를 선언해 주었다.

for(string s: cities){
    transform(s.begin(), s.end(), s.begin(), ::tolower);
    deque <string> ::iterator it = find(cache.begin(), cache.end(), s);
    if(it != cache.end()){
        cache.erase(it);
        cache.push_back(s);
        answer++;
    }
    else{
        if(cache.size() >= cacheSize) cache.pop_front();
        cache.push_back(s);
        answer += 5;
    }
}

 

그러고 나서 for문을 cities의 size만큼 돌아주었다.

transform(s.begin(), s.end(), s.begin(), ::tolower);
deque <string> ::iterator it = find(cache.begin(), cache.end(), s);

코드를 하나씩 뜯어보자면 제일 처음에 한 일은 똑같은 지역이라도 소문자로 올 수도 대문자로 올 수도 있으므로 일단 통일해주기 위해 다 소문자로 바꿔주었다. 그러고 나서 find함수로 cache에 해당 지역이 있는지 찾아주었다. (나는 여기서 for문 돌려 찾아 줄 생각을 했었는데 find함수를 쓰면 된다는 것을 깨달았다.)

if(it != cache.end()){
    cache.erase(it);
    cache.push_back(s);
    answer++;
}
else{
    if(cache.size() >= cacheSize) cache.pop_front();
    cache.push_back(s);
    answer += 5;
}

만약 없을 경우엔 cache.end() 값을 반환하기 때문에 cache.end()가 아닐 경우는 그 해당 위치에 원소를 지우고 맨 뒤에 데이터를 넣어주었다. 이 경우는 cache hit이므로 answer++를 해주었다.

 

아닐 경우는 만약 cache의 size가 cacheSize와 같으면 가장 오래된 데이터를 빼고 넣어야 하므로 deque자료구조의 특징을 살려 pop_front()를 해주었다. 그러고 나서 데이터를 뒤에 넣어주고 이 경우는 cache miss이므로 answer += 5를 해주었다.

 

이렇게 코드를 바꾸고 나니 효율이 약간 더 좋아진 것을 확인할 수 있었다.

바꾸기 전 코드	바꾼 코드

 

전체 코드

#include <string>
#include <deque>
#include <algorithm>

using namespace std;

int solution(int cacheSize, vector<string> cities) {
    
    int answer = 0;
    if(cacheSize == 0) return 5 * cities.size();
    
    deque <string> cache;
    
    for(string s: cities){
        transform(s.begin(), s.end(), s.begin(), ::tolower);
        deque <string> ::iterator it = find(cache.begin(), cache.end(), s);
        if(it != cache.end()){
            cache.erase(it);
            cache.push_back(s);
            answer++;
        }
        else{
            if(cache.size() == cacheSize) cache.pop_front();
            cache.push_back(s);
            answer += 5;
        }
    }
    
    return answer;
}