[프로그래머스 | 파이썬] 캐시(2018 KAKAO BLIND RECRUITMENT/ level 2)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/17680

프로그래머스

 

 

 

코드

def solution(cacheSize, cities):
    if cacheSize == 0:
        return len(cities) * 5
    else:
        answer = 0
        cities = [i.lower() for i in cities]
        stack = []
        for i in cities:
            if i not in stack:
                answer += 5
                if len(stack) == cacheSize:
                    stack.pop(0)
                stack.append(i)
            elif i in stack:
                stack.remove(i)
                stack.append(i)
                answer += 1
        return answer

 

 

 

코드 설명

1️⃣ 캐시 크기가 0인 경우 cities배열의 크기를 리턴하도록 한다.(예외 처리)

2️⃣ 캐시 크기가 0이 아닌 경우 아래 3️⃣ ~ 5️⃣를 수행한다.

3️⃣ cities의 모든 원소를 소문자로 변경한다.

4️⃣ 만약 stack 안에 cities의 원소가 없다면(=해당 원소에 접근한 적이 없다는 뜻) cache miss이므로 실행시간을 5초 추가한다. 이때 스택이 가득 차 있다면 가장 처음 접근한 원소를 삭제해 공간을 비워준다. 이후 스택에 cities의 원소를 추가해 해당 원소에 접근했음을 표시한다.

5️⃣ 만약 stack 안에 cities의 원소가 존재한다면, cache hit이므로 실행시간을 1초 추가한다. 또한 스택에서 해당 원소값을 삭제한 뒤 스택의 가장 맨 뒤에 추가해 해당 원소를 가장 마지막에 접근했음을 표시한다.

 

 

➕ 실패한 코드

 

def solution(cacheSize, cities):
    if cacheSize == 0:
        return len(cities) * 5
    else:
        answer = 0
        cities = [i.lower() for i in cities]
        print(cities)
        visit_idx = [0] * cacheSize
        ls = [cities[i] for i in range(cacheSize)]
        for i in range(cacheSize, len(cities)):
            if cities[i] not in ls:
                answer += 5
                ls[visit_idx.index(min(visit_idx))] = cities[i]
            elif cities[i] in ls:
                answer += 1
            print(ls)
            visit_idx[ls.index(cities[i])] += 1
            print(visit_idx)
        return answer + 5 * cacheSize

 

 [출력결과]

['jeju', 'pangyo', 'seoul', 'newyork', 'la', 'jeju', 'pangyo', 'seoul', 'newyork', 'la']
['newyork', 'pangyo', 'seoul']
[1, 0, 0]
['newyork', 'la', 'seoul']
[1, 1, 0]
['newyork', 'la', 'jeju']
[1, 1, 1]
['pangyo', 'la', 'jeju']
[2, 1, 1]
['pangyo', 'seoul', 'jeju']
[2, 2, 1]
['pangyo', 'seoul', 'newyork']
[2, 2, 2]
['la', 'seoul', 'newyork']
[3, 2, 2]

 

제출 전 예제는 모두 맞는데 제출해보면 4개 정도 틀린 정답이라고 나온다. 뭐가 잘못된 건지 모르겠다ㅠㅠ

틀린 풀이지만 오랜 시간동안 고민하고 작성한 코드라 그냥 버리기 아까워서 기록.

접근목록 리스트, 캐시 리스트 두개의 리스트를 만들어서, 접근 목록 리스트의 가장 접근횟수가 적은 인덱스를 구한 뒤 캐시리스트의 해당 인덱스(접근횟수가 가장 적은 인덱스)에 새로운 원소를 등록하는 식으로 구현.