프로그래머스
프로그래머스 [1차] 캐시(2018 KAKAO BLIND RECRUITMENT)
콩순이냉장고
2021. 9. 8. 15:04
문제 URL : https://programmers.co.kr/learn/courses/30/lessons/17680
코딩테스트 연습 - [1차] 캐시
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", "Ro
programmers.co.kr
문제 접근법 :
크게 어렵지않은문제입니다. LRU기법을 그대로 사용한문제지만 cachesize가 작기때문에 sort와 unorderd_map을 이용하여 lru와 같은 기법을 사용해도됩니다.
캐시미스일땐 인덱스가 가장작은것을찾아 제거하면되겠지요
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
//By 콩순이냉장고
#include <bits/stdc++.h>
using namespace std;
string lower(string s) {
string res;
for (int i = 0; i < s.size(); i++)
res += tolower(s[i]);
return res;
}
int solution(int cacheSize, vector<string> cities) {
int answer = 0;
unordered_map<string, int> se;
for (int i = 0; i < cities.size();i++) {
string s = lower(cities[i]);
if (se.count(s)) {
se[s] = i;
answer++;
}
else
{
if(se.size()>=cacheSize) {
vector<pair<int, string>> v;
for (auto it : se) {
v.push_back({ it.second,it.first });
}
sort(v.begin(), v.end());
if(!v.empty())
se.erase(v[0].second);
}
if(se.size()+1<=cacheSize)
se[s] = i;
answer += 5;
}
}
return answer;
}
|
cs |
궁금한점 혹은 모르는점 어떤질문이든 댓글은언제나 환영입니다.