[코테] 백준 1713번 : 후보 추천하기 (java)

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;
	}

}

 

---

❗결과