프로그래머스 캐시 (C++)

2018년도 카카오 공채 문제 - [1차] 캐시

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

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

전형적인 LRU(Least Recently Used) 알고리즘 문제.

리스트로도 구현이 가능한데, 고민하다가 덱으로 구현했다.

 

문제 풀이는 다음과 같다.

1. cities의 사이즈만큼 for문을 돌린다.

2. cities에 저장된 문자열을 문자열 변수 city에. 이때 문자열을 전부 대문자로 바꾸거나 소문자로 바꿔서 저장한다.

문제를 보면 알겠지만, cities의 문자열은 NewYork로 들어올수도 있고 newyork로 들어올수도 있기 때문이다.

3. 덱의 싸이즈만큼 for문을 돌린다. 만약 덱 안에 city와 동일한 문자열이 있다면 해당 위치에 있는 문자열을 제거해준다(erase 함수사용).

4. 덱에서 city를 지웠으면 정답을 +1 해준다.

5. 덱에서 city를 지우지 않았을 경우, 덱이 비어있지 않은 조건 & 덱의 사이즈가 cacheSize 이상이라는 조건 하에 덱의 맨 앞(가장 오래전에 들어온 값)을 지운다.

6. 덱의 맨 뒷자리에 city를 추가해준다.

#include <string>
#include <vector>
#include <deque>

using namespace std;

int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    deque<string> dq;
    for(int i=0; i<cities.size(); i++){
        string city = cities[i];
        bool ch = false;
        for(int j=0; j<city.size(); j++) city[j] = tolower(city[j]);
        for(int j=0; j<dq.size(); j++){
            if(dq[j]==city){
                dq.erase(dq.begin()+j);
                ch = true;
                break;
            }
        }
        if(ch) answer++;
        else{
            if(!dq.empty()&&dq.size()>=cacheSize) dq.pop_front();
            answer += 5;
        }
        if(cacheSize!=0) dq.push_back(city); // 주의
    }
    return answer;
}

주의 표시를 주목해야하는데, 만약 if(cacheSize!=0)조건을 추가하지 않으면 7번과 17번 테스트 케이스에서 실패를 겪는다.

cacheSize가 0이 아닌 경우에만 덱에 값을 추가할 수 있기 때문이다.