2024년 3월 18일 알고리즘 문제풀이
문제
난이도
Lv.2
코드
1차
80점 / 100점
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def solution(cacheSize, cities):
answer = 0
if not cacheSize:
answer = 5 * len(cities)
return answer
arr = []
for i in cities:
city = i.lower()
if len(arr) < cacheSize:
answer += 5
arr.append(city)
continue
if city in arr:
answer += 1
arr.remove(city)
arr.append(city)
continue
else:
answer += 5
arr.pop(0)
arr.append(city)
return answer
캐시에 여유공간이 있을 때는 우선적으로 채워주었다. 캐시가 가득 찼을 때, 가장 사용된지 오래된 캐시가 삭제되야 하므로 이에 대한 구별이 필요했다. 따라서 사용한 캐시는 배열에서 삭제후 다시 추가하였다. 이렇게 되면 캐시 배열의 0번 index의 값이 1순위로 삭제될 캐시가 된다. 테스트 케이스가 몇개 있어 실패하였는데, 생각해보니 캐시가 가득 차지 않았을 때도 이미 캐시에 존재하여 추가할 필요가 없는 경우가 있었다. 예를 들어, 첫 번째 두 번쨰 도시가 같다면 내 로직에선 둘 다 캐시에 들어 가버린다. 이 경우를 위해 조건을 추가했다.
2차
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def solution(cacheSize, cities):
answer = 0
# 캐시가 없을 떄는 모든 동작이 5초 걸리는 것으로 계산하여 결과 도출
if not cacheSize:
answer = 5 * len(cities)
return answer
# 캐시 배열
arr = []
for i in cities:
# 소문자로 통일
city = i.lower()
# 아직 캐시에 여유 자리가 있고, 캐시에 존재하지 않는 도시인 경우만 캐시에 추가한다.
if len(arr) < cacheSize and city not in arr:
answer += 5
arr.append(city)
continue
# 캐시에 여유자리가 없거나, 여유 자리가 있지만 이미 캐시에 존재하는 도시의 경우 로직의 흐름
# 캐시에 있는 도시의 경우 캐시에서 가장 마지막 index로 설정해준다.
if city in arr:
answer += 1
arr.remove(city)
arr.append(city)
continue
# 캐시에 없을 경우 0번 index를 삭제하고 새로운 캐시를 마지막 index에 추가해준다.
else:
answer += 5
arr.pop(0)
arr.append(city)
return answer
