[Baekjoon] 1713_후보 추천하기

Silver I

문제(출처: https://www.acmicpc.net/problem/1713)

---

< 후보 추천하기 >

 

문제 풀이 

 

ArrayList를 2개 사용해서 문제를 해결했다. 하나는 사진의 정보인 사진 번호, 추천 수, 게시된 순서를 저장하며 다른 하나에는 사진틀에 게재된 사진의 번호만 저장한다.

 

학생을 추천하면, 이미 사진틀에 게시된 사진인지 확인 후 게시되어 있다면 추천 수를 증가한다. 이미 사진틀에 게시되어 있지 않고 사진틀이 꽉 차있다면 추천수가 가장 적고, 오래된 사진을 제거하고 다른 사진을 게시한다.

 

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;

public class _1713_ { // 후보 추천하기
	static class Draw {
		private int person;
		private int cnt;
		private int seq;

		private Draw(int person, int cnt, int seq) {
			this.person = person;
			this.cnt = cnt;
			this.seq = seq;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		int n = Integer.parseInt(bf.readLine());
		int m = Integer.parseInt(bf.readLine());

		ArrayList<Draw> list = new ArrayList<>();
		ArrayList<Integer> arr = new ArrayList<>();
		int idx = 0;

		st = new StringTokenizer(bf.readLine());
		for (int i = 0; i < m; i++) {
			int num = Integer.parseInt(st.nextToken());
			if (arr.contains(num)) {
				for (int j = 0; j < list.size(); j++) {
					if (list.get(j).person == num) {
						list.get(j).cnt += 1;
					}
				}
			} else {
				if (list.size() >= n) {
					Collections.sort(list, new Comparator<Draw>() {
						@Override
						public int compare(Draw o1, Draw o2) {
							if (o1.cnt == o2.cnt) {
								return o1.seq - o2.seq;
							}
							return o1.cnt - o2.cnt;
						}
					});
					Draw draw = list.remove(0);
					arr.remove(Integer.valueOf(draw.person));
				}
				arr.add(num);
				list.add(new Draw(num, 1, idx++));
			}
		}

		Collections.sort(arr);

		for (int i = 0; i < arr.size(); i++) {
			bw.write(arr.get(i) + " ");
		}
		bw.flush();
	}
}

 

Main

변수)
Draw : [학생 번호, 추천 수, 게시된 순서]
n : 사진틀 개수
m : 추천 횟수
list : ArrayList <Draw>
arr : ArrayList <사진틀에 게시된 사진 번호>
idx : 게시된 순서

 

사진틀의 개수(n)와 전체 학생의총 추천 횟수(m)를 입력받는다.

 

추천받은 학생을 나타내는 번호를 입력(num) 받은 후 사진틀에 이미 게시되어 있는 사진이라면 그 사진의 추천 수를 증가한다. 하지만 사진틀에 없는 학생의 사진이라면 사진틀이 꽉 차있는지를 먼저 확인한다. 사진틀이 꽉 차있다면 사진의 추천수를 오름차순으로, 추천 수가 같다면 게시된 순서가 오래된 순서인 오름차순으로 정렬한 후 추천수가 낮고, 오래된 사진을 제거한다. 그 후에 새로운 사진을 게시한다.

 

최종 게시된 사진을 오름차순으로 정렬 후 출력한다. 

---

---