#1. 문제
#2. 풀이
1. unordered_map 컨테이너
unordered_map 컨테이너는 C++ 표준라이브러리에서 제공하는 비 순차 연관 컨테이너입니다. um 컨테이너는 키와 값을 쌍으로 해시 자료구조에 저장하며, 중복을 허용하지 않고 정렬 상태를 유지하지 않습니다.
2. LRU(Least Recently Used)
LRU는 캐싱 전략 중 하나로 가장 최근에 사용되지 않은 데이터를 우선적으로 Swap(캐시 Miss 발생 시 필요한 데이터를 기존의 캐시에 저장된 데이터와 교체하는 작업)합니다. 따라서, LRU는 기본적으로 시간 지역성(Temporal Locality)에 기반합니다.
3. HIT? +1초 & 현재 시간 추가, MISS? +5초 LRU 기반의 SWAP!
- 먼저, transform() 알고리즘을 통해 도시 이름을 모두 소문자로 변환합니다.
- um 컨테이너(해시 자료구조)에 현재 도시 이름을 키 값으로 find() 알고리즘을 수행하고, 찾았다면 HIT, 못 찾았으면 MISS로 분기합니다.
- HIT의 경우, 최종 소요 시간에 +1 해주고, 현재 도시에 대한 가장 최근 접근 시간을 현재 시간으로 업데이트해줍니다.
- MISS의 경우, 최종 소요 시간에 +5 해주고, um 컨테이너를 순회하며 가장 최근에 접근하지 않은 도시를 찾아 삭제해 주고, 현재 도시와 현재 시간을 쌍으로 um컨테이너에 삽입해 줍니다.
- 최종 소요 시간을 결과 값으로 반환해 줍니다.
#3. 코드
#include <string>
#include <vector>
#include <climits>
#include <algorithm>
#include <unordered_map>
using namespace std;
int solution(int cacheSize, vector<string> cities) {
if(cacheSize == 0)
{
return 5*(int)cities.size();
}
int answer = 0;
// { city_name, last_used }
unordered_map<string, int> cache;
for(int i=0; i<(int)cities.size(); ++i)
{
transform(cities[i].begin(), cities[i].end(), cities[i].begin(), ::tolower);
auto it = cache.find(cities[i]);
// #1. Hit : +1 실행 시간
if(it != end(cache))
{
answer += 1;
it->second = i;
}
// #2. Miss : +5 실행 시간
else
{
answer += 5;
// cache가 비어있지 않을 때
if(!cache.empty()&& (int)cache.size() == cacheSize)
{
// #1. LRU 수행
int minHit = INT_MAX;
string minHitCity = "";
for(auto it = begin(cache); it != end(cache); ++it)
{
if(it->second < minHit)
{
minHitCity = it->first;
minHit = it->second;
}
}
cache.erase(minHitCity);
}
cache.insert({cities[i], i});
}
}
return answer;
}
'문제 풀이 > Programmers 문제 풀이' 카테고리의 다른 글
[Programmers]#Level2_프로세스, 큐, 우선순위 큐 (0) | 2024.04.08 |
---|---|
[Programmers]#Level2_기능 개발, 스택, ceil(), 실수와 정수의 혼용 연산 (0) | 2024.03.21 |
[Programmers]#Level2_땅 따먹기, DP (0) | 2024.03.21 |
[Programmers]#Level2_의상, 해시, unordered_map (0) | 2024.03.21 |
[Programmers]#Level2_주식가격, 스택, 히스토그램 유형 (0) | 2024.03.21 |