[프로그래머스] [1차] 캐시 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

프로그래머스

 

1. 문제 설명

2. 풀이과정

1. 리스트보다 연산 속도가 빠르고 popleft() 메서드를 사용할 수 있는 deque 자료구조를 사용하기 위해 deque 모듈을 불러온다. from collections import deque
2. 먼저 도시 이름을 저장해 둘 deque을 생성한다. memory = deque()
3. 도시 이름을 하나씩 추출하여 for i in cities
4. 도시 이름 사이에 대소문자 구별이 없으므로 모두 소문자로 변환해 준다. i = i.lower()
5. 만약 도시 이름이 앞에서 나온 적 있다면 if (i in memory)
6. chche hit 이므로 실행 시간에 1을 추가한다. answer += 1
7. 그리고 해당 도시 이름을 삭제하고 memory.remove(i)
8. 제일 뒤에 다시 추가해 준다. memory.append(i)
9. 이것은 LRU 알고리즘에 의해 나중에 도시 이름을 저장해 둘 deque이 꽉 찼을 경우 가장 오랫동안 사용하지 않았던 도시 이름을 앞에서부터 제거하기 위한 과정입니다.
10. 반면에 도시 이름이 처음 나왔다면 else
11. cache miss 이므로 실행 시간에 5를 추가한다. answer += 5
12. 그리고 도시 이름을 제일 뒤에 추가한다. memory.append(i)
13. 만약 deque 안의 원소 도시 이름 개수가 cacheSize 보다 크면(메모리 초과) if (len(memory) > cacheSize)
14. 가장 오랫동안 사용하지 않은 원소인 제일 앞 원소를 제거한다. memory.popleft()

반응형

3. 소스코드

from collections import deque

def solution(cacheSize, cities):
    answer = 0
    
    memory = deque()
    for i in cities:
        i = i.lower()
        if (i in memory):
            answer += 1
            memory.remove(i)
            memory.append(i)
        else:
            answer += 5
            memory.append(i)
            if (len(memory) > cacheSize):
                memory.popleft()
            
    return answer