문제 탐색하기
입력 자료 정리
- n은 사진들의 개수로 검증으로 활용될 입력값이다
- k는 이후 들어오는 원소값들의 개수로 시뮬레이션의 횟수가 될 것이다
- 이후 들어오는 각 원소는 추천하는 후보의 번호로 규칙을 위해 활용될 원소들이다
해결방법 추론
- 1~4번까지만 보면 먼저 입력값들을 다 기록해두고,
우선순위 큐 하나를 활용하는 간단한 자료구조 문제라고 생각했다 - 하지만 5번을 보고나서 먼저 입력값을 받는 것이 아니라
시뮬레이션으로 입력이 들어올 때마다 실시간 업데이트를 해주어야 한다는 것을 알게 되었다 - 따라서 본래 생각했던 방법을 바꿔 미리 자료구조를 세팅해두고,
시뮬레이션으로 입력값들에 대해 규칙을 만족시키도록 해야겠다고 생각하였다 - 일단 규칙에서 비교가 되는 요소는 두가지이다.
하나는 최초 추천시간이며, 하나는 추천받은 횟수이다 - 전체 후보는 100명이므로 각 후보별로 가장 처음에 받은 추천시간과 추천수를
배열로 관리해야겠다고 생각하였다.
클래스로 묶지 않고, 배열로 각각에 대해 관리해야겠다고 생각한 이유는 이후 사용할
우선순위 큐에서 편리하게 정렬되도록 하기 위함이다 - 우선순위 큐를 사진틀로 생각해서 입력값이 들어올 때마다 추천횟수가 가장 낮고,
추천횟수가 같을 경우 추천받은 시간이 느릴수록 앞으로 가도록 한 뒤,
만약 사진틀이 n만큼 꽉차서 빼야하는 순간이 온다면 바로 뺄 수 있도록 한다면
쉽게 해결할 수 있을 것이다!
시간복잡도 계산
- 입력값이 들어오는 k번의 연산이 발생할 것이고,
이중 우선순위 큐의 num값을 remove할 것이기 때문에,
이 부분에서 우선순위 큐의 크기만큼의 시간이 발생한다. - 최악의 경우 pq에 20명의 후보가 들어가 있을 것이기 때문에,
시간복잡도는 O(k * 20)이 될 것이며, 총 추천 횟수가 1000번 이하이므로
시간제한안에 문제를 해결할 수 있다
코드 설계하기
자료구조 설계
- int형 타입의 배열을 두개 선언한다. 101의 크기를 갖는 배열이며,
각 배열별로 인덱스(후보)의 최초 추천받은 시간과 추천수를 관리한다. - 우선순위 큐는 Integer 타입의 값을 관리한다
이때, 정렬은 추천수를 관리하는 배열의 오름차순으로 정렬하며, 같을 경우
최근 추천 받은 시간을 기준으로 오름차순 정렬을 한다.
간단하게 람다식으로 선언하였다
입력값 시뮬레이션 진행
- StringTokenizer로 들어오는 값은 이후 계속 사용되므로, int형 타입의 변수에 저장한다
- 이때 들어오는 값은 후보의 번호이므로 배열에서 인덱스로 활용한다
- 먼저 후보의 추천수를 증가시켜준다. 배열에서 입력값을 인덱스로 하여 값을 증가시켜준다
- 두가지 분기로 나누어서 판단한다. 우선순위 큐에 해당 후보가 있는가 없는가로 구분해야한다
- 만약 없다면 추천 받은 시간을 현재 탐색 i로 배열에 초기화하며,
우선순위 큐의 크기가 n과 같은지를 검사한다. - 같다면 5번 조건을 위해 횟수를 관리하는 배열의 인덱스로
우선순위 큐의 맨앞 값을 poll()한 경우로 하여 0으로 초기화한다 - 이어서 조건을 벗어나서 우선순위 큐에 현재 후보의 번호를 넣어준다
- 만약 있다면 갱신을 위해 우선순위 큐에서 해당 번호를 찾아 지워주고, 다시 넣어준다.
출력 설계
- 완성한 후보를 오름차순으로 출력해야한다.
따라서 ArrayList에 우선순위 큐 값을 넣은 다음 오름차순 정렬을 진행하였다 - 정렬된 리스트 값들을 뽑아 출력하면 정답이 된다
정답 코드
(1회차 시도 성공!)
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
int k = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
int[] time = new int[101];
int[] counts = new int[101];
PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> {
if(counts[o1] == counts[o2]){
return time[o1] - time[o2];
}
return counts[o1] - counts[o2];
});
for (int i = 0; i < k; i++) {
int num = Integer.parseInt(st.nextToken());
counts[num]++;
if(!pq.contains(num)){
time[num] = i;
if(pq.size() == n){
counts[pq.poll()] = 0;
}
pq.add(num);
}else{
pq.remove(num);
pq.add(num);
}
}
List<Integer> list = new ArrayList<>(pq);
Collections.sort(list);
for (Integer i : list) {
bw.write(i + " ");
}
br.close();
bw.close();
}
}
문제 링크
Software Developer