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

문제

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

 

리뷰

자료구조 및 알고리즘

Least Recently Used → 벡터와 같은 자료구조에서 Hit일 경우 remove and push back을 통해 '리뉴얼' 함으로써 삭제를 방지

 

문제 풀이에서의 핵심 포인트

1. Hit/Miss에 대한 case 구현하기: 굳이 몇 번 Hit되었는지 count할 필요 없이, Hit일 경우 remove and push back
2. 대/소문자 구별 없이 처리하기:
   - cpp reference가 사용가능하다면 아래와 같은 함수(ToLower) 제작
   - 사용이 안 된다면 #include <string> strcasecmp(a.c_str(), b.c_str()) == 0 을 이용
3. Cache size == 0일 때의 예외 처리 구현하기

// case 1.
string ToLower(string s){
    transform(s.begin(), s.end(), s.begin(),
             [](unsigned char c){ return std::tolower(c); }
             );
    return s;
}

// case 2.
if(strcasecmp(a.c_str(), b.c_str()) == 0){
	...
}

 

구현 코드

#include <cstring>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

string ToLower(string s){
    transform(s.begin(), s.end(), s.begin(),
             [](unsigned char c){ return std::tolower(c); }
             );
    return s;
}

// 2차 풀이
int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    vector<string> cache;
  
    for(int c=0; c<cities.size(); c++){
        bool found_flag = false;
        int found_idx = -1;
        // 0. lower case
        
        string city_now = ToLower(cities[c]);
        //string city_now = cities[c];
        for(int i=0; i<cache.size(); i++){
            if(cache[i] == city_now){
            
            //if(strcasecmp(cache[i].c_str(), city_now.c_str()) == 0){
                found_flag = true;
                found_idx = i;
                break;
            }
        }
        
        // 1. cache hit
        if(found_flag){
            // remove and push again
            cache.erase(cache.begin()+found_idx);
            cache.push_back(city_now);
            answer += 1;
        }
        // 2. cache miss
        else{
            if(cacheSize == 0){
                answer += 5;
                continue;
            }
            // 2-1. cache not full
            //if(cache.size() < cacheSize){}
            // 2-2. cache full
            if(cache.size() >= cacheSize)
                cache.erase(cache.begin());
            
            cache.push_back(city_now);
            answer += 5;
        }
    }    
    return answer;
}