2018 카카오 코딩테스트 1차 캐시 JS 문제풀이

🔗직접 문제 풀러가기

 

입력

• 캐시크기 n과 도시이름 배열 cities를 입력받는다.
• 0 <= n <= 30
• cities.length <= 100,000
• 각 도시이름은 영문자로만 이뤄져있고, 대소문자를 구분하지 않는다.

출력

• 도시이름 배열을 순서대로 처리할 때 필요한 총 실행시간을 반환한다.

조건

• 캐시 교체 알고리즘은 가장 최근에 참조된 페이지를 캐시에 담고있는 LRU(Least Recently Used)를 사용.
• cache hit 일 경우 실행시간은 1
• cache miss 일 경우 실행시간은 5

 

문제풀이

 

 

 

m = cities.length

n = 0 <= cache.size <= 30

시간복잡도: O(nm) = O(m)

공간복잡도: O(n) = O(1)

 

 

 

문제에서 n이 30이하로 제한되어있어서 상수 취급 할 수 있지만, 만약 n의 크기가 최적화가 필요할 만큼 크거나 크기의 제한이 없다면 캐쉬를 배열이 아닌 집합으로 구현하는게 훨씬 효율적이기 때문에 집합으로 다시 구현해보았다.

 

.values()는 삽입된 순서대로 값들을 가지고 있는 iterator object을 반환한다.

 

m = cities.length

n =  0 <= cache.size <= 30

시간복잡도: O(m) 

공간복잡도: O(n) = O(1)