[프로그래머스] 캐시(LRU, list, map) - ☆

#문제링크 : programmers.co.kr/learn/courses/30/lessons/17680

<전략>

1. 블로그를 참고했습니다.

2. 리스트와 맵을 이용하여 구현한다. 리스트는 들어온 문자열을 담는 실제 캐시의 역할, 리스트에서 임의의 값을 삭제하는 것은 가능하지만, 임의의 값을 찾는 것은 O(N)만큼의 시간이 걸린다. 왜냐하면, 순차적으로 내가 찾으려는 값과 같은 값인지 반복자를 하나씩 증가시켜가며 찾아야하기 때문. 따라서, 맵의 find 함수를 사용해서 더 수월하고 빠르게 찾기 위해 맵을 사용한다. 임의의 값을 찾는 행위가 필요한 이유는, 캐시에 새로들어오는 문자열이 캐시 안에 이미 존재하는지, 아닌지 확인하기 위함이다.

3. 맵을 통해, 새로 들어온 값이 이미 캐시안에 존재하는지 확인하고, 

ⓐ 존재하지 않으면서 캐시가 가득 찼다면, 리스트의 가장 뒤에 위치한 값을 버린다. map에서도 해당값을 버린다.

ⓑ 존재한다면, map을 통해 해당값을 찾아 리스트에서 버린다. 

[공통] a, b 경우 이후에 공통적으로 리스트 앞에 새로운 문자열을 삽입하고, 맵에도 넣어준다.

4. map은 <string, list<string>::iterator> 형으로 선언한다. 리스트에서 임의의 값을 지우기 위해서는 해당 값의 반복자가 필요한데, list.erase( "반복자" ); 를 하기 위함. 지우려는 키값의 문자열을 맵에 넣으면 위치한 반복자를 알려주기 때문에, 훨씬 간단한 코드로 문제를 해결할 수 있다.

5. LRU 알고리즘에 대해 알고 있어야 한다.

※주의사항

1. list는 임의의 값이 어디에 위치했는지 바로 알 수 없다. -> 순차적으로 찾아나가야 한다.

2. 반복자는 순서를 저장하는게 아니라, 그 값의 주소와 같다고 생각하면 된다.

3. list의 erase 함수는 입력으로 "반복자"를 받는다. 

4. 캐시의 크기가 0인 경우를 고려하자.

Code