[1차]캐시(29분)

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

구현 아이디어 13분 구현 17분

풀이

구현 문제를 풀고 나면 풀이가... 너무 마음에 들지 않는다.

#include <string>
#include <vector>
#include <queue>

using namespace std;

struct Data
{
    string name;
    int sec;
    Data(string n, int s)
    {
        name = n;
        sec = s;
    }
    bool operator<(const Data& b) const
    {
        if(sec != b.sec) return sec > b.sec;
        return false;
    }
};

int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    
    priority_queue<Data> pQ;
    int cur_sec = 0;
    
    if(cacheSize == 0)
    {
        cur_sec = cities.size() * 5;
        return cur_sec;
    }
    
    // 대소문자 구분을 안한다...
    int N = cities.size();
    for(int i = 0; i < N; ++i)
    {
        // 우선순위 큐가 비어있을 경우 캐시 미스.
        if(pQ.empty())
        {
            // 캐시 미스.
            pQ.push(Data(cities[i], cur_sec));
            cur_sec += 5;
        }
        else
        {
            // 큐에 있는 것들을 꺼내보며 캐시 힛인지 확인해야 함.
            bool hit = false;
            
            // 꺼낸 캐시 잠깐 저장하는 큐.
            // 나중에 우선순위 큐에 옮기면 정렬하기 때문에 큐에 넣어도 됨.
            queue<Data> store;
            while(!pQ.empty())
            {
                // 가장 오래 전에 쓰인 캐시.
                Data b = pQ.top();
                pQ.pop();
                
                // 대소문자 구분 없이 비교.
                for(int j = 0; j < cities[i].length(); ++j)
                {
                    // 길이가 다르면 무조건 다른 도시.
                    if(b.name.length() != cities[i].length())
                    {
                        hit = false;
                        store.push(b);
                        break;
                    }
                    else if(b.name[j] == cities[i][j] ||
                            b.name[j] + 32 == cities[i][j] ||
                            b.name[j] - 32 == cities[i][j] ||
                            b.name[j] == cities[i][j] + 32 ||
                            b.name[j] == cities[i][j] - 32)
                    {
                        hit = true;
                        continue;
                    }
                    // 위 조건문에 들어가지 않아도 다른 도시.
                    else
                    {
                        hit = false;
                        store.push(b);
                        break;
                    }
                }
                if(hit)
                {
                    // 캐시 힛.
                    // 참조된 현재 시간으로 갱신해서 우선순위 큐에 push.
                    b.sec = cur_sec;
                    pQ.push(b);
                    cur_sec += 1;
                    break;
                }
            }
            
            // store에 담았던 Data 다시 우선순위 큐에 담음.
            while(!store.empty())
            {
                pQ.push(store.front());
                store.pop();
            }
            
            // hit이 false인 경우에 캐시 미스.
            if(hit == false)
            {
                // 사이즈가 같다면 top 빼고 push.
                if(pQ.size() >= cacheSize)
                { 
                    pQ.pop();
                    pQ.push(Data(cities[i], cur_sec));
                }
                // 사이즈가 작다면 바로 push.
                else
                    pQ.push(Data(cities[i], cur_sec));
               
                cur_sec += 5;
            }
        }
    }
    
    return answer = cur_sec;
}

---

풀이

좋은 아이디어를 봤다. 도시 이름을 전부 소문자로 변환한 뒤에 도시 이름을 비교하면 아래와 같은 구문은 필요없다.

else if(b.name[j] == cities[i][j] ||
                            b.name[j] + 32 == cities[i][j] ||
                            b.name[j] - 32 == cities[i][j] ||
                            b.name[j] == cities[i][j] + 32 ||
                            b.name[j] == cities[i][j] - 32) continue;

앞과 뒤에서 빼거나 넣을 수 있는 deque를 사용해서 다시 푼 풀이. 채점 시간이 엄청나게 줄었다. 도시가 100,000개나 입력되기 때문에 소문자 변환이 효율적이었다. 그리고 우선순위 큐로 정렬하지 않고 deque를 활용해 가장 최근에 참조된 캐시를 앞에 두는 풀이법이라 효율적이라 생각한다.

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

using namespace std;

int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    
    if(cacheSize == 0)
        return cities.size() * 5;
    
    int N = cities.size();
    
    for(auto& city : cities)
    {
        for(int i = 0; i < city.length(); ++i)
            if(isupper(city[i])) city[i] += 32;
    }
    
    deque<string> dQ;
    for(int i = 0; i < N; ++i)
    {
        if(dQ.empty())
        {
            dQ.push_front(cities[i]);
            answer += 5;
        }
        else
        {
            bool find = false;
            for(int j = 0; j < dQ.size(); ++j)
            {
                if(cities[i] == dQ[j])
                {
                    dQ.erase(dQ.begin() + j);
                    dQ.push_front(cities[i]);
                    answer += 1;
                    find = true;
                    break;
                }
            }
            
            if(!find)
            {
                if(dQ.size() < cacheSize)
                {
                    dQ.push_front(cities[i]);
                }
                else
                {
                    dQ.pop_back();
                    dQ.push_front(cities[i]);
                }
                    
                answer += 5;
            }
        }
    }
    
    return answer;
}