링크 : https://school.programmers.co.kr/learn/courses/30/lessons/17680
문제 설명
캐시 크기에 따른 실행 시간을 측정하는 프로그램을 작성하시오.
캐시크키(cacheSize)와 도시이름 배열(cities)을 입력받습니다. (최대 캐시 사이즈 30, 최대 도시 수 10만개입니다)
각 도시 이름은 영문자로만 구성되어 있으며, 대소문자를 구분하지 않습니다.
캐시에 도시가 있어 캐시hit라면 1, 캐시에 도시가 없어 캐시 miss라면 5에 시간이 걸립니다.
캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용합니다.
* 페이지 교체 알고리즘(페이징 기법) : https://snikuz.tistory.com/78#002
FIFO(First In First Out) : 적재된 시간을 기준으로 페이지를 교체. 가장 먼저 할당한 페이지를 교체.
LFU(Leaset Frequently Used) : 최소 빈도로, 가장 사용 횟수가 적은 페이지를 교체.
LRU(Leaset Recently Used) : 가장 오래전에 참조된, 가장 안쓰던 페이지를 교체.
OPT(Optimal) : 앞으로 사용하지 않을 페이지를 교체.
아이디어
1. 대소문자 구분이 없다 → 대소문자 통일을 시켜야 할 것 같습니다.
2. 딕셔너리를 캐시용도로 쓰려고 합니다. 매 반복마다 모든 캐시에 사용 안된 턴을 증가합니다.
3. 캐시 사용시 턴을 초기화합니다.
4. 캐시가 꽉 찼다면 캐시 내에 가장 오래동안 사용 안한 캐시를 찾아 교체합니다.
코드
#include <bits/stdc++.h>
using namespace std;
int solution(int cacheSize, vector<string> cities) {
//캐시 사이즈 0일 때 예외처리
if(cacheSize == 0) return cities.size() * 5;
int answer = 0;
unordered_map<string, int> m;
for(auto& city : cities)
{
//대소문자 통일
for(int i = 0; i < city.size(); i++)
city[i] = tolower(city[i]);
if(m.find(city) == m.end())
{
if(m.size() < cacheSize)
{
m[city] = 0;
}
else
{
pair<string, int> target {"", -1};
for(const auto& [key, value] : m)
{
if(target.second < value)
{
target.first = key;
target.second = value;
}
}
m.erase(target.first);
m[city] = 0;
}
answer += 5;
}
else
{
m[city] = 0;
answer += 1;
}
for(auto& [key, value] : m)
++value;
}
return answer;
}
메모리 4.17MB, 시간 0.49ms
'알고리즘' 카테고리의 다른 글
프로그래머스 - 파일명 정리 (0) | 2024.05.28 |
---|---|
프로그래머스 - 방문길이 (0) | 2024.05.27 |
프로그래머스 - PCCP 모의고사 2회 - 신입사원 교육 (0) | 2024.05.26 |
프로그래머스 - 모음사전 (0) | 2024.05.15 |
프로그래머스 - 과제 진행하기 (0) | 2024.05.08 |