https://www.acmicpc.net/problem/1713
알고리즘 분류 : 구현, 시뮬레이션
❓문제
🔅해석
학생 객체에 학생 번호, 추천 수, 타임스탬프를 저장하여 조건에 맞게 정렬을 한다.
Student[] students = new Student[101]; //학생 번호는 1부터 100까지의 자연수이다.
학생 객체를 담는 배열을 만들어 학생 번호와 배열 인덱스를 맞춰 저장한다.
예를 들어, 2번 학생이 추천을 받았을 때 배열 2번째에 학생 객체가 존재한다면 이미 추천받아 저장되어 있다는 것이다.
이 때는 해당 객체의 추천수를 증가시킨다.
List<Student> photos = new ArrayList<>(); // 사진틀의 개수 N를 저장한다.
배열이 비어있다면 사진틀 리스트에 추가해준다.
이 때 사진 틀이 꽉 찼을 때, 아래와 같은 조건에 따라 삭제 후 추가한다.
1. 추천 수가 가장 적은 학생을 삭제한다.
2. 추천 수가 같은 경우, 게시가 가장 오래된 사진을 삭제한다.
3. 게시된 사진이 삭제되는 경우에는 해당 학생의 추천 수를 0으로 바꾼다.
위 조건에 따라 리스트를 추천 수 오름차순, 타임스탬프 오름차순을 하면 될 것 같지만, ArrayList 의 특성을 살펴보면 앞에서 삭제하는건 앞을 삭제하고 뒤에서 땡겨와야하기에 O(N)만큼 걸린다.
맨 뒤에서 삭제한다면, O(1)의 시간복잡도를 가진다. 그래서 내림차순 정렬을 하여 제일 먼저 삭제될 학생을 리스트 뒤에 놓는다.
⭕정답 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int M = Integer.parseInt(br.readLine());
List<Student> photos = new ArrayList<>();
Student[] students = new Student[101];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < M; i++) {
int num = Integer.parseInt(st.nextToken());
// 사진 추가
if (students[num] != null) { // 사진틀 존재
// 이미 형성된 학생
students[num].cnt++;
} else { // 사진틀 존재 하지 않음
// 사진틀 꽉 참
// 정렬
Collections.sort(photos);
if (photos.size() == N) {
// 사진 삭제
Student del = photos.remove(N - 1);
students[del.num] = null;
}
// 새로운 학생
students[num] = new Student(num, 1, i);
photos.add(students[num]);
}
}
// photos 출력
Collections.sort(photos, (o1, o2) -> o1.num - o2.num);
for (Student s : photos) {
System.out.print(s.num + " ");
}
br.close();
}
}
class Student implements Comparable<Student> {
int num;
int cnt;
int timeStamp;
public Student(int num, int cnt, int timeStamp) {
super();
this.num = num;
this.cnt = cnt;
this.timeStamp = timeStamp;
}
// 추천횟수 내림차순, 시간 내림차순 정렬
@Override
public int compareTo(Student s2) {
int resultCnt = s2.cnt - cnt;
if (resultCnt == 0) {
return s2.timeStamp - timeStamp;
}
return resultCnt;
}
}
❗결과
'코딩테스트 > 백준' 카테고리의 다른 글
[코테] 백준 2805번 : 나무 자르기 (java) (0) | 2024.08.03 |
---|---|
[코테] 백준 2003번 : 수들의 합 2 (java) (0) | 2024.08.03 |
[코테] 백준 1256번 : 사전 (java) (0) | 2024.08.03 |
[코테] 백준 1837번 : 암호제작 (java) (0) | 2024.08.03 |
[코테] 백준 3955번 : 캔디 분배 (java) (0) | 2024.08.03 |