3번문제로 넘어오겠습니다. 3번 문제는 블로그의 설명에 따르면 난이도를 '하' 로 설정했음에도 많은 사람들이 맞추지 못했다며 '여기서 부터 많이 어려웠나 봅니다' 라는 내용이 나옵니다. 그리고 밑에 부연설명을 해놓은 것이 있었는데, 제가 이해한 것이 맞다면 아마 외부 소스를 검색해서 사용해도 문제가 없는(!) 형태의 시험이었나 봅니다. 굉장히 신기하네요..
문제를 요약하면, 캐시 메모리가 있는데 캐시 메모리가 꽉 찼을 때 LRU 알고리즘, 가장 오래전에 사용된 항목을 지우고 캐시를 입력하면 된다가 핵심입니다. 즉 이 문제에서 해결을 해야 되는 부분은
1) 도시가 100,000 개 까지 들어오기 때문에 $O(n)$ 으로 중복검사를 하면 필연적으로 TLE가 발생한다. 따라서 더 빠른 시간 내에 도시의 중복 여부를 검색해야 한다.
2) cache hit 시 사용된 시기를 갱신하여 나중에 LRU 알고리즘 적용시에도 가장 오래된 항목을 찾을 때 $O(cachesize)$ 보다 빠르게 찾아야 한다.
가 핵심이 되겠습니다. 여기서 우리는 입력받은 자료들을 단순히 선형으로 관리하면 안된다는 것을 알게 됩니다. 여기서는 트리 구조로 관리를 하여 로그 시간 복잡도 이내에 검색과 갱신을 진행해야 된다는 점을 알아두시면 될 것 같습니다.
임의의 한 시간대에는 1개의 자료만 들어오므로 시간대가 독립적이라는 것이 보장됩니다. 따라서 C++ 기준 key와 value로 해쉬를 할 수 있는 map 자료구조를 이용하여 이를 구현할 수 있습니다. cache size가 30이므로 value로 검색을 할 경우 선형 검색을 하더라도 시간 초과가 날 것 같지는 않지만, 완벽을 위해 value를 별도로 관리하는 자료 구조를 하나 더 추가하겠습니다. 이렇게 구현하면 평균적인 복잡도는 $nlog(n)$이 됩니다.
int solve(int cacheSize, vector<string> cities)
{
const int CACHE_HIT = 1, CACHE_MISS = 5;
if (!cacheSize)
{
return cities.size() * CACHE_MISS;
}
int ans = 0, time = 0;
map<int, string> cache1;
map<string, int> cache2;
for (string city : cities)
{
time++;
if (!cache2[city])
{
ans += CACHE_MISS;
}
else
{
ans += CACHE_HIT;
}
if (cache1.size() == cacheSize)
{
auto elem = *cache1.begin();
cache2.erase(elem.second);
cache1.erase(elem.first);
}
cache1[time] = city;
cache2[city] = time;
}
return ans;
}