[1차] 캐시 c++

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

 

 

 

문제

---

• 지도개발팀에서 근무하는 제이지는 지도에서 도시 이름을 검색하면 해당 도시와 관련된 맛집 게시물들을 데이터베이스에서 읽어 보여주는 서비스를 개발하고 있다.
• 이 프로그램의 테스팅 업무를 담당하고 있는 어피치는 서비스를 오픈하기 전 각 로직에 대한 성능 측정을 수행하였는데, 제이지가 작성한 부분 중 데이터베이스에서 게시물을 가져오는 부분의 실행시간이 너무 오래 걸린다는 것을 알게 되었다.
• 어피치는 제이지에게 해당 로직을 개선하라고 닦달하기 시작하였고, 제이지는 DB 캐시를 적용하여 성능 개선을 시도하고 있지만 캐시 크기를 얼마로 해야 효율적인지 몰라 난감한 상황이다.
• 어피치에게 시달리는 제이지를 도와, DB 캐시를 적용할 때 캐시 크기에 따른 실행시간 측정 프로그램을 작성하시오.

 

 

 

 

 

입출력

---

 

캐시	도시이름(cities)	실행시간
3	["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"]	50
3	["Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul"]	21
2	["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"]	60
5	["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"]	52
2	["Jeju", "Pangyo", "NewYork", "newyork"]	16
0	["Jeju", "Pangyo", "Seoul", "NewYork", "LA"]	25

 

 

 

접근법

---

1. 문제 설명이 뭔가 친절 한듯 하지만 역시나, 주구장창 설명하는 문제이기에, 정리하자면, 주어진 vector 배열(도시이름)에서, 캐시에 해당하는 Queue 자료 구조에, 다음 입력이 있으면 cache hit 해서 +1 , 없으면 cache miss 해서 +5 를 적용하여 계산하는 문제이다.
2. 별다른 건 없고, queue 자료 구조 보단, 순회 가능한 list 를 써서, find( ) 알고리즘을 쓸 수 있도록 하였으며,
3. "new York" 과 "New York" 등 lowercase 로 통일해줘야 하는 문제가 있기에, 처음 부분을 transform( ) 시켜주었다.

 

#include <string>
#include <vector>
#include <algorithm>
#include <cctype>
#include <list>
#include <iostream>
#include <set>

using namespace std;

int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    list<string> city_name;
    transform(cities.begin(), cities.end(), cities.begin(), 
              [](string& city){
                transform(city.begin(), city.end(), city.begin(), [](unsigned char c){ return tolower(c);});\
                return city;
    });
    
    for (auto& e: cities) {
        if(find(city_name.begin(), city_name.end(), e) != city_name.end() ) {
            answer += 1;
        } else{
            answer += 5;
        }
        if (cacheSize == 0) 
            continue;
        if (city_name.size() == cacheSize)
            city_name.pop_front();
        city_name.push_back(e);
    }
    return answer;
}