BOJ 1713 후보 추천하기 (Java)
문제 탐색하기
- 학생들이 추천을 시작하기 전에 모든 사진틀은 비어있다.
- 어떤 학생이 특정 학생을 추천하면, 추천받은 학생의 사진이 반드시 사진틀에 게시되어야 한다.
- 비어있는 사진틀이 없는 경우에는 현재까지 추천 받은 횟수가 가장 적은 학생의 사진을 삭제하고, 그 자리에 새롭게 추천받은 학생의 사진을 게시한다.
- 이때, 현재까지 추천 받은 횟수가 가장 적은 학생이 두 명 이상일 경우에는 그러한 학생들 중 게시된 지 가장 오래된 사진을 삭제한다.
- 현재 사진이 게시된 학생이 다른 학생의 추천을 받은 경우에는 추천받은 횟수만 증가시킨다.
- 사진틀에 게시된 사진이 삭제되는 경우에는 해당 학생이 추천받은 횟수는 0으로 바뀐다.
캐시 LFU를 실제로 구현하고, 동률인 경우 그 중에 가장 오랫동안 참고(추천)하지 않은 경우를 계산하는 문제이다.
코드 설계하기
구현 방법
- LinkedHashMap을 활용한 데이터 저장
LinkedHashMap<Integer, Integer>을 사용하여 학생 번호와 해당 학생이 받은 추천 횟수를 저장한다.LinkedHashMap을 사용함으로써 삽입 순서를 유지한다.- 가장 오래된(먼저 추가된) 학생을 제거할 때 유용하다.
- 추천 처리
- 이미 등록된 학생이면 추천 횟수를 증가시킨다.
- 새롭게 등록해야 하는 학생이지만 사진틀에 자리가 있다면 추가한다.
- 사진틀이 가득 찬 경우, LFU(Least Frequently Used) 정책을 적용하여 가장 추천 횟수가 적은 학생을 제거한다.
- 추천 횟수가 같은 경우, 먼저 등록된 학생을 제거해야 하므로
LinkedHashMap의 순서를 유지하는 특성을 활용한다. - 최소 추천 횟수를 가진 학생을 찾기 위해
reduce()를 사용하여 최소값을 가진 엔트리를 찾아 제거한다.
- 추천 횟수가 같은 경우, 먼저 등록된 학생을 제거해야 하므로
- 결과 출력 : 최종적으로 남은 학생들의 번호를
sorted()를 이용해 정렬 후 출력한다.
시간 복잡도
추천 처리
- **이미 존재하는 학생 추천 시 (
**map.containsKey(tmp)**)LinkedHashMap에서containsKey()및put()을 사용하는 경우 O(1)
- 새로운 학생 추천 시
map.size() == N인 경우 최소 추천 횟수를 가진 학생을 찾아 제거한다.entrySet().stream().reduce(...)를 이용하여 최소 추천 횟수를 찾는 과정은 O(N)- 제거 후
put()을 수행하는 것은 O(1)
따라서 최악의 경우, 모든 K개의 추천이 새 학생에 대한 추천이고, 매번 LFU 제거 연산이 필요하다고 하면 시간 복잡도는 O(K * N) 이 된다.
정렬 및 출력
map.keySet().stream().sorted()를 사용하여 오름차순 정렬하므로 O(N log N)- 정렬된 키 값을
forEach()로 출력 -> O(N)
최종 시간 복잡도
최악의 경우:
- 추천 처리: O(K * N)
- 정렬 및 출력: O(N log N)
따라서 전체 시간 복잡도는 O(K * N + N log N) 이고, 최악의 경우 연산 횟수는 약 1,000 × 20 = 20,000 이므로 시간 내에 연산이 가능하다.
시도 회차 별 수정사항(Optional)
첫 번째 추천과 두번째 혹은 세번째 추천을 받는 후보가 동일한 경우를 고려하지 않았다. 다음과 같이 구현하게 되면 첫 후보의 추천 수가 증가하지 않게 되고, 삭제된다.
# 입력
5
7
1 1 2 3 4 5 6
# 기대 결과
1 3 4 5 6
# 결과
2 3 4 5 6
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedHashMap;
import java.util.StringTokenizer;
public class b1713 {
private static int N, K;
private static LinkedHashMap<Integer, Integer> map = new LinkedHashMap<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
K = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
for (int i = 0; i < K; i++){
int tmp = Integer.parseInt(st.nextToken());
if (map.size() < N){
map.put(tmp, 1);
}else {
if (!map.containsKey(tmp) && map.size() == N){
map.entrySet().stream()
.reduce((e1, e2) -> e1.getValue() <= e2.getValue() ? e1 : e2)
.ifPresent(e -> map.remove(e.getKey()));
}
map.put(tmp, map.getOrDefault(tmp, 0) + 1);
}
}
map.keySet().stream().sorted().forEach(i -> System.out.print(i + " "));
}
}
정답 코드 (Java)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedHashMap;
import java.util.StringTokenizer;
public class b1713 {
private static int N, K;
private static LinkedHashMap<Integer, Integer> map = new LinkedHashMap<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
K = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
for (int i = 0; i < K; i++){
int tmp = Integer.parseInt(st.nextToken());
// 이미 해당 값이 존재하는 경우를 먼저 체크한다.
if (map.containsKey(tmp)){
map.put(tmp, map.get(tmp)+1);
} else {
// map 길이가 N이 된 경우, 알고리즘에 따라 지워질 값 체크
if (map.size() == N){
map.entrySet().stream()
.reduce((e1, e2) -> e1.getValue() <= e2.getValue() ? e1 : e2)
.ifPresent(e -> map.remove(e.getKey()));
}
map.put(tmp, map.getOrDefault(tmp, 0) + 1);
}
}
// 키 값에 따라 정렬된 순서대로 출력한다.
map.keySet().stream().sorted().forEach(i -> System.out.print(i + " "));
}
}
보자마자 캐시 생각이 먼저 떠올라서 map으로 구현했는데 Student 객체 내에 후보 번호와 현재 게시 순서, 추천 수를 필드로 받고 우선순위 큐로 구현해도 무방할 것 같다.
Leave a comment