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

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

프로그래머스

캐시에 대해서 안다면 문제 이해는 어렵지 않았다.

다만 내가 벡터에 대해 이해가 많이 부족했던 것같다.

auto, vector<string>::iterator, tolower(), find(), erase() 에 대해서 알고 써본 적이 있지만 아무것도 안보고 하려니까 제대로 아는 것이 없었다.

제대로 아는 것이 아니였다는 것을 깨달았다.

또한 예외 부분을 찾는 것이 어려웠다. 캐시사이즈가 0이 될때를 생각을 못해서 틀렸다.

 

풀이

1. 도시의 이름을 소문자로 바꾼다.

2. 캐시에 저장이 되어 있는지 확인한다.

3.저장이 되어있지 않다면 캐시에 도시이름을 저장한다. 캐시가 다 차있다면 맨 앞에 들어있는 도시를 삭제하고 넣어준다.

4.저장이 되어 있다면 삭제하고 맨 뒤에 넣어준다.     * LRU(Least Recently Used)이기 떄문에

다른 사람 풀이 중

deque를 사용한 사람도 있었다. 처음 들어보는 자료구조인데 벡터와 유사하지만 앞으로도 원소를 추가, 삭제할 수 있다.

또한 벡터는 메모리가 찼을 때  메모리 재할당 후 이전 원소를 복사하는 방식으로 인하여,  삽입시에 성능이 저하 하는 단점이 있지만 deque는 메모리 블럭을 하나 새로 할당한다.

원소를 앞쪽으로 추가/삭제 하려면 deque.push_front(원소), deque.pop_front(원소)를 사용하면 된다. 뒤로 추가/삭제하는 방법은 벡터랑 똑같다.

#include <string>
#include <vector>
#include <algorithm>
#include <cctype>

using namespace std;

int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    
    vector<string>cache(cacheSize);
    int cityN=cities.size();
    if(cacheSize==0)
        return cityN*5;
    for(int i=0;i<cityN;i++)
    {
        
        //소문자로 바꾸기
        for(int j=0;j<cities[i].size();j++)
                cities[i][j]=tolower(cities[i][j]);
        
        auto it=find(cache.begin(),cache.end(),cities[i]);//vector<string>::iterator it
        if(it==cache.end())
        {   ///캐시 용량이 다 차고 캐시가 비어있지 않을때
            if(cache.size()==cacheSize&&cache.size()>0)
                cache.erase(cache.begin());//삭제
              
            //새로운 도시를 캐시에 넣어줌
            cache.push_back(cities[i]);
            answer+=5;//실행시간
        }
        else
        {
            cache.erase(it);//cache.begin()+(it-cache.begin()));
            cache.push_back(cities[i]);
            answer+=1;
        }
    }
    return answer;
}