[프로그래머스/Python] 캐시

Sujin Lee·2022년 10월 7일
0

코딩테스트

목록 보기
131/172
post-thumbnail

문제

프로그래머스 - 캐시

문제 이해

  • 캐시 교체 알고리즘: LRU(Least Recently Used)
    • 가장 오래된 페이지를 교체하는 알고리즘
    • 자료구조의 큐와 같이 선입선출 형태
    1. 새로운 데이터가 들어온 경우
      • 캐시에 넣어준다.
      • 캐시가 가득차있다면, 가장 오래된 데이터를 제거하고 넣어준다.
    2. 존재하는 데이터가 들어온 경우
      • 해당 데이터를 꺼낸 뒤
      • 가장 최근 데이터 위치로 보내준다.
  • cache hit: 참고하고자 하는 메모리가 캐시에 존재하는 경우
  • cache miss: 참고하고자 하는 메모리가 캐시에 존재하지 않는 경우

해결 과정

  • cache 빈 배열을 만든다.
  • .lower() : city는 대소문자를 구별하지않으므로 for문을 돌며 cache배열에 접근할 때 모두 소문자로 변경하여 저장한다.
  • cacheSize가 0인 경우 cache 저장 불가능 -> cache miss -> time += 5
  • cacheSize가 0이 아닌 경우 cache에 데이터가 있는지 확인
    • 이미 있으면 = cache hit -> 해당 데이터를 빼주고 최근 위치(뒤)에 넣어준다. -> time += 1
    • 없으면 = cache miss -> cache의 사이즈를 비교 -> time += 5
      • cacheSizecache의 길이가 같으면 가장 오래된 데이터를 빼주고 새로 넣는다.
      • 길이가 작으면 바로 넣는다.

풀이

def solution(cacheSize, cities):
    time = 0
    cache = []
    for i in cities:
        i = i.lower()
        if cacheSize != 0:
            if i not in cache:
                if len(cache) == cacheSize:
                    cache.pop(0)    
                cache.append(i)
                time += 5
            else:
                cache.pop(cache.index(i))
                cache.append(i)
                time += 1
        else:
            time += 5
            
    return time
profile
공부한 내용을 기록하는 공간입니다. 📝

0개의 댓글