[백준] S2 1713 후보 추천하기 (java)

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

1713번: 후보 추천하기

 

풀이

 

1) 후보는 최대 100명이므로 int형 배열 student[100] 을 만든다.

2) 투표지를 개봉할 때마다 리스트를 탐색하여 해당 후보가 있을경우와 없을경우로 나눈다

2-1) 해당 후보가 있을경우 (student[i] > 0) 리스트 값을 갱신한다.

2-2) 해당 후보가 없을경우 list의 크기가 사진틀의 개수보다 작을경우와 클 작지 않을 경우로 나눈다.

2-2-1) 작을 경우 그냥 추가만 해준다

2-2-2) 클 경우 투표수가 가장 낮은 후보를 없애고 (student[] = 0, list.remove(0)) 새 후보를 추가한다.

3) student를 탐색하여 0 이상인 학생을 출력한다.

 

주의사항

 

1) 중복 검사를 사진틀 갯수 검사 보다 먼저해야한다. => 안하면 1, 1, 1 같은 결과가 나올 수 있음

 

package com.baekJoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class BJ_S2_1713_후보추천하기 {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	public static void main(String[] args) throws NumberFormatException, IOException {
		input = new BufferedReader(new StringReader(src));
		int N = Integer.parseInt(input.readLine());
		int recommend = Integer.parseInt(input.readLine());
		int vote[] = new int [recommend];
		tokens = new StringTokenizer(input.readLine());
		for(int i=0; i<recommend; i++) {
			vote[i] = Integer.parseInt(tokens.nextToken());
		}
		solution(N, recommend, vote);
	}

	private static void solution(int N, int recommend, int vote[]) {
		int student[] = new int[101];
		List<Node> list = new ArrayList<>();
		for(int i=0; i<recommend; i++) {
			if(student[vote[i]] != 0) {
				student[vote[i]]++;
				for(int j=0; j<list.size(); j++) {
					if(list.get(j).student == vote[i]) {
						list.get(j).count++;
						break;
					}
				}
			}else {
				student[vote[i]]++;
				if(list.size() >= N) {
					Collections.sort(list);
					student[list.get(0).student] = 0;
					list.remove(0);
					list.add(new Node(i, vote[i], 1));
				}else {
					list.add(new Node(i, vote[i], 1));
				}
			}
		}
		for(int i=0; i<student.length; i++) {
			if(student[i]!=0) {
				System.out.print(i+" ");
			}
		}
	}
	
	static class Node implements Comparable<Node>{
		int no;
		int student;
		int count;
		
		public Node(int no, int student, int count) {
			super();
			this.no = no;
			this.student = student;
			this.count = count;
		}
		@Override
		public int compareTo(Node o) {
			if(this.count == o.count) {
				return Integer.compare(this.no, o.no);
			}
			return Integer.compare(this.count, o.count);
		}
		@Override
		public String toString() {
			return "Node [no=" + no + ", student=" + student + ", count=" + count + "]";
		}
		
	}

	static String src =
			"3\r\n"
			+ "14\r\n"
			+ "2 1 4 3 5 6 2 7 2 100 100 54 54 50";
}

 

후기

 

 생각보다 어렵게 풀었다. 내가 시뮬레이션이 약하다고 느끼게되었다. 첫 코드는 한줄한줄이 너무 비효율적이었다. 예를들어 마지막 출력 시 list에서 하나씩 꺼내서 배열에 담아서 정렬하고 출력을 했지만 생각해보니 student배열만 검색하면 되었다.