LRU 캐시는 가장 최근에 사용되지 않은 캐시를 교체하는 알고리즘이니까 priority_queue 로 구현하였다. pair 자료구조는 기본적으로 first 값 내림차순으로 구현 되기때문에 먼저 들어간 캐시를 top 에 두기 위해서는 캐시가 등록된 시간에 -1 을 곱하면 간단하게 구현할 수 있다.
모든 도시들을 한바퀴 순회하면서 캐시를 확인하고 있다면 answer++, 없다면 answer+=5 이다.
cache miss 가 났다면 새롭게 캐시를 등록해주어야 한다. 단순하게 cache.pop() 하면 가장 오래된 캐시를 지울 수 있다. 여기서 캐시사이즈를 체크해주어야함.
cache hit 가 났다면 새롭게 추가하지 않고 기존 캐시에 들은 시간값을 현재 시간으로 업데이트 해야한다. priority_queue 를 한바퀴 돌면서 city 값이 일치하는 캐시를 찾아야하기 때문에 O(M) 만큼의 시간이 들것이다.
hit 든 miss 든 cache 에 값을 삽입하는건 log(M) 이다. 전체 cities 수만큼 반복하면서 그안에서 cache 를 순회하면서 hit 판별, 그리고 push 혹은 update 를 하는데 이연산은 O(M) 그래서 전체 시간복잡도는 O(NlogM) 이다.
17680. 캐시
문제링크
설계
최대 도시수는 100,000 이기 때문에
O(N^2)미만으로 풀도록 해보자.도시수 : N,
캐시사이즈 : M
LRU캐시는 가장 최근에 사용되지 않은 캐시를 교체하는 알고리즘이니까priority_queue로 구현하였다.pair자료구조는 기본적으로first값 내림차순으로 구현 되기때문에 먼저 들어간 캐시를top에 두기 위해서는 캐시가 등록된 시간에-1을 곱하면 간단하게 구현할 수 있다.모든 도시들을 한바퀴 순회하면서 캐시를 확인하고 있다면
answer++, 없다면answer+=5이다.cache miss가 났다면 새롭게 캐시를 등록해주어야 한다. 단순하게cache.pop()하면 가장 오래된 캐시를 지울 수 있다. 여기서 캐시사이즈를 체크해주어야함.cache hit가 났다면 새롭게 추가하지 않고 기존 캐시에 들은 시간값을 현재 시간으로 업데이트 해야한다.priority_queue를 한바퀴 돌면서city값이 일치하는 캐시를 찾아야하기 때문에O(M)만큼의 시간이 들것이다.hit든miss든 cache 에 값을 삽입하는건log(M)이다. 전체cities수만큼 반복하면서 그안에서cache를 순회하면서hit판별, 그리고push혹은update를 하는데 이연산은O(M)그래서 전체 시간복잡도는O(NlogM)이다.시간복잡도
O(NlogM)