프로그래머스 - [1차] 캐시

Posted on | In |

오늘의 문제

2018 KAKAO BLIND RECRUITMENT > [1차] 캐시

DB 캐시를 적용할 때 캐시 크기에 따른 실행시간 측정 프로그램을 작성하시오.

입력형식

  1. 캐시 크기(cacheSize)와 도시이름 배열(cities)을 입력받는다.
  2. cacheSize는 정수이며, 범위는 0 ≦ cacheSize ≦ 30 이다.
  3. cities는 도시 이름으로 이뤄진 문자열 배열로, 최대 도시 수는 100,000개이다.
  4. 각 도시 이름은 공백, 숫자, 특수문자 등이 없는 영문자로 구성되며, 대소문자 구분을 하지 않는다. 도시 이름은 최대 20자로 이루어져 있다.

출력형식

입력된 도시이름 배열을 순서대로 처리할 때, 총 실행시간을 출력한다

조건

  • 캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용한다.
  • cache hit일 경우 실행시간은 1이다.
  • cache miss일 경우 실행시간은 5이다.

풀이 방법 - 오답

1
2
3
4
5
6
7
8
9
10
11
12
13
init_cities = len(set(cities[:cacheSize])) * 5 + len(cities[:cacheSize]) - (len(set(cities[:cacheSize])))

for i in range(0, len(cities)):
    try:
        checkCity = cities[cacheSize + i]
        if checkCity in cities[0+i: cacheSize+i]:
            init_cities += 1
        else:
            init_cities += 5
    except IndexError as e:
        pass

init_cities

사담

알고리즘 조건을 정확하게 맞추지 못해서 에러가 나는듯 하다. 근데 테스트 케이스도 다 맞고 … ㅠ 이럴 때 제일 난감하다… 진짜 두뇌 회전을 요하는 그런 …ㅋㅋ 그냥 풀면 안 될까요?