알고리즘 스터디 0310

➡️ 캐시

def solution(cacheSize, cities):
    if not cacheSize:                       # 1. cacheSize가 아예 없는 경우 - 테스트 6,7,17 런타임에러
        return len(cities)*5
    time = 0
    cache = []
    for city in cities:         
        city = city.lower()                 # 대소문자 구분 없도록, 소문자로 처리
        if city in cache:                   # 2. cahce hit : 참고하는 도시가 cache 안에 있는 경우
            cache.pop(cache.index(city))
            cache.append(city)    
            time +=1
        else:
            if len(cache)>=cacheSize: # 3. cache miss : 참고하느 도시가 cache 안에 없는 경우
                cache.pop(0)
            cache.append(city)
            time +=5

    return 

첫번째 조건문에서 city가 캐시에 있다면 순서를 다시 조정해줘야하므로 pop하고 다시 append
캐시 순서가 중요한거지 횟수가 중요한 게 아니라서 그냥 이렇게 풀었으면 됐을 것 같다 ㅠㅠ
근데 이건 스택이나 큐는 아닌 것 같다 그냥 리스트로 간단하게 풀 수 있었던 걸루
뭐가 중요한 건지 꼭 먼저 파악해야겠다

➡️ 캐시 힙

➡️ 최소힙

import heapq
import sys

# n = 9
n = int(sys.stdin.readline())

# x = [0, 12345678, 1, 2, 0, 0, 0, 0, 32]
x = [int(sys.stdin.readline()) for _ in range(n)]

array = []

heapq.heapify(array)

for item in x:
    if item == 0 and array:
        data = heapq.heappop(array)
        print(data)
    elif item == 0 and not array:
        print(0)
    
    else:
        heapq.heappush(array, item)

나는 for 문안에서 하나씩 값을 읽어서 넣어줬는데
한번에 리스트로 받아서 이후에 for문 안에서 하나씩 꺼내 쓰는 방식으로 했다
array는 굳이 heapify를 할 필요는 없는 것 같다