[프로그래머스] [1차] 캐시 (파이썬)

🗓️ 문제 설명

• 캐시 크기(cacheSize)와 도시이름 배열(cities)가 주어지고 입력된  도시이름 배열을 순서대로 처리할 때, 발생한 총 실행시간을 출력하는 코드를 작성해주세요.
• 캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용하여 cache hit일 경우에는 실행시간이 1이고, cache miss일 경우에는 실행시간은 5입니다.
• 제한 사항
  • cacheSize는 정수이며, 범위는 0 ≤ cacheSize ≤ 30
  • cities는 도시 이름으로 이뤄진 문자열 배열, 최대 도시 수는 100,000개
  • 각 도시 이름은 공백, 숫자, 특수문자 등이 없는 영문자로 구성되며, 대소문자 구분은 없음
  • 도시 이름은 최대 20자
• 입출력 예시

캐시크기(cacheSize)	도시이름(cities)	실행시간
3	["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"]	50
3	["Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul"]	21
2	["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"]	60
5	["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"]	52
2	["Jeju", "Pangyo", "NewYork", "newyork"]	16
0	["Jeju", "Pangyo", "Seoul", "NewYork", "LA"]	25

 

💻 코드

최종 코드

 

코드 풀이

 

다른 사람 풀이

풀이 1번

1. 2~3번줄 : 최대 길이를 cacheSize로 지정한 deque 생성
2. 5번줄 : 도시 배열에서 도시를 하나씩 꺼내는 반복문 실행
3. 6번줄 : 도시를 소문자로 저장
4. 7~8번줄 : 도시가 캐시에 있다면 도시를 제거하고, 도시를 다시 추가
5. 10번줄 : 시간에 1을 더함
6. 11~12번줄 : 도시가 캐시에 없다면 도시를 추가
7. 13번줄 : 시간에 5를 더함

 

 

알게된 점

• LRU(Least Recently Used) 알고리즘 : 가장 오랫동안 참조되지 않은 페이지를 교체하는 기법
  • 캐시가 사용하는 리소스의 양이 제한되어 있고, 캐시는 제한된 리스트 내에서 데이터를 빠르게 접근할 수 있어야 함
  • 장점
    • 빠른 액세스 : 가장 최근에 사용한 아이템부터 정렬
    • 빠른 업데이트 : 하나의 아이템에 액세스 할때마다 업데이트
  • 단점
    • 많은 공간 차지