백준 1713번: 후보 추천하기

문제 설명

• https://www.acmicpc.net/problem/1713

접근법

• 이미 걸려있는 사진에 투표했을 경우 때문에 PriorityQueue가 아닌 List를 사용했습니다.
  • i번째 걸려있는 사진의 투표수를 높이려면 i번째 값에 접근할 수 있어야 하는데 PriorityQueue는 .get(i)가 존재하지 않습니다.
• 추천횟수를 기준으로 정렬합니다. 추천횟수가 같을 경우 게시된 시간을 기준으로 정렬해 가장 앞에 값을 제거합니다.
• Comparator를 Implements했다면 Collections.sort()를 사용할 수 없습니다.

Collections.sort에서 Comparator로 정렬하는 방법

Collections.sort(list, new Comparator<Vote>() {
	@Override
	public int compare(Vote a, Vote b) {
		return a.num - b.num;
	}
});

람다식으로 정렬하는 방법

PriorityQueue<Node> pq = new PriorityQueue<>((a,b)->a.w - b.w)

정답

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		int[] arr = new int[M];
		for (int i = 0; i < M; i++) {
			arr[i] = sc.nextInt();
		}

		List<Vote> list = new LinkedList<Vote>();
		for (int i = 0; i < arr.length; i++) {
			if (list.size() == N) {
				boolean flag = false;
				for (int j = 0; j < N; j++) {
					if (arr[i] == list.get(j).num) {
						flag = true;
						list.get(j).vote_num++;
						break;
					}

				}
				if (!flag) {
					list.remove(0);
					list.add(new Vote(arr[i], 1, i));
				}
			} else {
				boolean flag = false;
				for (int j = 0; j < list.size(); j++) {
					if (arr[i] == list.get(j).num) {
						flag = true;
						list.get(j).vote_num++;
						break;
					}

				}
				if (!flag) {
					list.add(new Vote(arr[i], 1, i));
				}
			}
			Collections.sort(list);
		}

		// Vote와 다른 기준으로 정렬
		Collections.sort(list, new Comparator<Vote>() {
			@Override
			public int compare(Vote a, Vote b) {
				return a.num - b.num;
			}
		});
		
		
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < list.size(); i++) {
			sb.append(Integer.toString(list.get(i).num) + " ");
		}
		System.out.println(sb.toString());
	}

	static class Vote implements Comparable<Vote> {
		int num;
		int vote_num;
		int hanged_time;

		public Vote(int num, int vote_num, int hanged_time) {
			super();
			this.num = num;
			this.vote_num = vote_num;
			this.hanged_time = hanged_time;
		}

		@Override
		public String toString() {
			return "Vote [num=" + num + ", vote_num=" + vote_num + ", hanged_time=" + hanged_time + "]";
		}

		@Override
		public int compareTo(Vote o) {
			// TODO Auto-generated method stub
			return (this.vote_num == o.vote_num) ? this.hanged_time - o.hanged_time : this.vote_num - o.vote_num;
		}

	}
}