프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
의식의 흐름
도시 이름을 넣고 빼고 해야할 것 같으니까 덱을 쓰면 되지 않으려나.. 일단 cacheSize만큼 넣고 채운 이후에 포함하는지 안하는지에 따라서 나누면 될 것 같은데
=> 실행 결과 : 틀렸습니다.
왜..?하면서 다시 생각해보니 "일단 cachesize만큼 넣고 채운 이후에"가 잘못된 생각이었다. cacheSize만큼 채우기 전에도 도시 이름을 포함하고 있는지 아닌지에 따라 넣고 빼야했다. 해당 부분을 수정하고 나니 통과
풀이
1. cacheSize가 0인 경우, 무조건 cachemiss가 나기 때문에 5*cities.length만큼의 시간이 걸린다.
2. cacheSize>0인 경우, 도시 이름이 덱에 포함되지 않은 경우, 포함된 경우를 나눠서 처리한다.
-> 도시 이름이 덱에 포함된 경우,
덱에서 해당 도시 이름을 제거하고 맨 뒤에 다시 넣는다. 이때 시간은 +1
-> 도시 이름이 덱에 포함되지 않은 경우,
-> 이미 cacheSize만큼 덱을 채운 경우, 맨 앞에 있는 도시 이름을 빼고 새로운 도시 이름을 맨 뒤에 넣는다.
-> 덱을 덜 채운 경우, 맨 뒤에 도시 이름을 넣는다.
이때 시간은 +5
코드
import java.util.*;
class Solution {
public int solution(int cacheSize, String[] cities) {
int answer = 0;
if(cacheSize == 0) // cachaeSize가 0인 경우
answer = 5*cities.length; // 무조건 cache miss
else{
Deque<String> deque = new ArrayDeque<>();
for(int i=0;i<cities.length;i++){
String city = cities[i].toLowerCase();
if(deque.contains(city)){ // deque에 도시 이름 있는 경우
// 해당 도시 이름 맨 뒤로 보내기
deque.remove(city);
deque.addLast(city);
answer += 1;
}
else{ // deque에 도시 이름 없는 경우
if(deque.size() == cacheSize){ // 이미 cachsize만큼 넣어둔 경우
// 가장 앞에 있는 도시 이름 빼고 새로운 도시 이름 넣기
deque.removeFirst();
deque.addLast(city);
answer += 5;
}
else{
deque.addLast(city);
answer += 5;
}
}
}
}
return answer;
}
}
'알고리즘 > 프로그래머스' 카테고리의 다른 글
[JAVA] 프로그래머스 - 거스름돈 (0) | 2023.11.23 |
---|---|
[JAVA] 프로그래머스 - [3차]압축 (0) | 2023.05.03 |
[JAVA] 프로그래머스 - 튜플 (0) | 2023.05.01 |
[JAVA] 프로그래머스 - 귤 고르기 (0) | 2023.05.01 |