[2018 KAKAO BLIND RECRUITMENT] 캐시(C++)

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

코딩테스트 연습 - [1차] 캐시 | 프로그래머스

 

 

이 문제는 간단하게 논리를 구현할 수 있었다.

하지만 무려 한시간이나 걸렸다... 그 이유는 뒤에서 설명한다.

75점 나오는 사람 필독!

 

 

 

---

 

 

이 문제의 핵심은 LRU를 구현하는 것이다.

 

 

LRU를 구현하기 위해서는, 캐쉬의 자료구조에서 순서를 기억하고 있어야 한다.

 

 

순서를 기억하는 자료구조로는 queue를 사용할 수 있다.

 

 

하지만, queue는 원소를 삭제하기 위해서는 pop() 함수만 가능하므로, Hit된 원소의 순서를 바꿔주기에는 한계가 있다.

 

 

순서를 바꾸기 위해서는 해당 원소를 찾아서 삭제해야되기 때문이다.

 

 

queue의 순서를 유지하는 성격을 그대로 가지면서, erase까지 할 수 있는 자료구조가 있을까?

 

 

있다!

정답은 deque에 있다.

 

 

 

---

http://www.cplusplus.com/reference/deque/deque/?kw=deque

 

deque - C++ Reference

 

 

deque 자료구조는 위에 C++ Reference를 보면 알겠지만, 매우 좋다.

---

 

 

자 이제, 이 Deque를 이용해서 코드를 구현하면 되는데,

 

 

 

내가 실수한 부분을 소개하겠다.

 

 

   for (int i = 0; i < cities.size(); i++) {

        cities[i] = make_lowercase(cities[i]);

 

        bool check = false;

        for (deque<string>::iterator it = deq.begin(); it != deq.end(); it++) {

            if (cities[i].compare(*it) == 0) {

                deq.erase(it);

                // deq.push_back((*it));

 

                deq.push_back(cities[i]);

                answer += 1;

                check = true;

                break;

            }

        }

 

        if (!check) {

            if (deq.size() == cacheSize)

                deq.pop_front();

            deq.push_back(cities[i]);

            answer += 5;

        }

    }

 

// deq.push_back((*it))이 잘못된 부분이다. 이전에 주석을 걸어놓았다. 위에는 정상적으로 작동되는 코드이다.

 

 

이 코드의 주석을 해제하고, 채점을 해보면 75점이 나올 것이다.

 

 

처음 이 부분을 발견하고, cout << (*it) << endl로 테스트 케이스를 풀어봤는데 일부 테스트 케이스는 정상적으로 출력이 되는 것을 확인했다.

 

 

하지만, 4번 테스트 케이스를 이해하다보면, 반복자(it)는 가장 첫번째 원소를 가르키게 된다.

 

 

 

 

즉, deque에서 반복자로 erase하면, 그 반복자는 첫번째 원소를 가르킨다.

 

 

 

 

반복자를 이용한 삭제 연산은 반복자의 재사용에 주의해야 한다. 모든 자료구조에 해당된다!

 

 

 

---

 

 

 

해설코드(C++)

 

#include <string>

#include <vector>

#include <deque>

#include <iostream>

 

using namespace std;

 

string make_lowercase(string str) {

    for (int i = 0; i < str.size(); i++) {

        if (str[i] >= 'A' && str[i] <= 'Z')

            str[i] += 32;

    }

 

    return str;

}

 

int solution(int cacheSize, vector<string> cities) {

    int answer = 0;

    deque<string> deq;

 

    if (cacheSize == 0)

        return cities.size() * 5;

 

    for (int i = 0; i < cities.size(); i++) {

        cities[i] = make_lowercase(cities[i]);

 

        bool check = false;

        for (deque<string>::iterator it = deq.begin(); it != deq.end(); it++) {

            if (cities[i].compare(*it) == 0) {

                deq.erase(it);

                deq.push_back(cities[i]);

                answer += 1;

                check = true;

                break;

            }

        }

 

        if (!check) {

            if (deq.size() == cacheSize)

                deq.pop_front();

            deq.push_back(cities[i]);

            answer += 5;

        }

    }

 

    return answer;

}

 

 

 

---