[백준_1713번] 후보 추천하기

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

1713번: 후보 추천하기

[문제]

 월드초등학교 학생회장 후보는 일정 기간 동안 전체 학생의 추천에 의하여 정해진 수만큼 선정된다. 그래서 학교 홈페이지에 추천받은 학생의 사진을 게시할 수 있는 사진틀을 후보의 수만큼 만들었다. 추천받은 학생의 사진을 사진틀에 게시하고 추천받은 횟수를 표시하는 규칙은 다음과 같다.

 

1. 학생들이 추천을 시작하기 전에 모든 사진틀은 비어있다.
2. 어떤 학생이 특정 학생을 추천하면, 추천받은 학생의 사진이 반드시 사진틀에 게시되어야 한다.
3. 비어있는 사진틀이 없는 경우에는 현재까지 추천 받은 횟수가 가장 적은 학생의 사진을 삭제하고, 그 자리에 새롭게 추천받은 학생의 사진을 게시한다. 이때, 현재까지 추천 받은 횟수가 가장 적은 학생이 두 명 이상일 경우에는 그러한 학생들 중 게시된 지 가장 오래된 사진을 삭제한다.
4. 현재 사진이 게시된 학생이 다른 학생의 추천을 받은 경우에는 추천받은 횟수만 증가시킨다.
5. 사진틀에 게시된 사진이 삭제되는 경우에는 해당 학생이 추천받은 횟수는 0으로 바뀐다.

 후보의 수 즉, 사진틀의 개수와 전체 학생의 추천 결과가 추천받은 순서대로 주어졌을 때, 최종 후보가 누구인지 결정하는 프로그램을 작성하시오.

 

[입력 조건]

 첫째 줄에는 사진틀의 개수 N이 주어진다. (1 ≤ N ≤ 20) 둘째 줄에는 전체 학생의 총 추천 횟수가 주어지고, 셋째 줄에는 추천받은 학생을 나타내는 번호가 빈 칸을 사이에 두고 추천받은 순서대로 주어진다. 총 추천 횟수는 1,000번 이하이며 학생을 나타내는 번호는 1부터 100까지의 자연수이다.

 

[코드]

import java.util.*;

class Student_1713 implements Comparable<Student_1713>{
	int number,total,time;
	
	public Student_1713(int number,int total,int time) {
		this.number=number;
		this.total=total;
		this.time=time;
	}
	
	/*
	 * 해당 클래스를 저장하는 연결리스트를 정렬하면 
	 * 총 추천 횟수가 가장 작으면서 동시에 등록된 시간도 작은 클래스가 연결리스트의 가장 앞에 오게 된다. 
	 * 즉, 오름차순으로 정렬된다. 
	 */
	@Override
	public int compareTo(Student_1713 o) {
		// 총 추천 횟수가 같다면 등록된 시간을 기준으로 정렬
		if(this.total==o.total)
			return this.time-o.time;
		
		// 총 추천 횟수를 기준으로 정렬 
		return this.total-o.total;
	}
	
}
public class BaekJoon_1713 {
	static int n,m;
	static int[] student=new int[101]; // 각 학생의 총 추천 횟수를 저장하는 배열
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		m=sc.nextInt();
		ArrayList<Student_1713> list=new ArrayList<>(); // 액자가 걸린 학생들의 정보를 저장하는 연결리스트
		
		for(int i=0;i<m;i++) {
			int recommand=sc.nextInt(); // 추천하고자 하는 학생의 번호
			/*
			 * 추천한 학생의 추천 횟수가 0이 아니라면 이미 액자에 걸려있는 경우
			 * 액자에서 삭제되는 순간 추천 횟수도 0으로 초기화 되기 때문
			 */
			if(student[recommand]>0) {
				student[recommand]+=1; // 추천 횟수 추가
				for(int j=0;j<list.size();j++) {
					// 리스트에 추천된 학생의 번호를 찾아 총 추천 횟수 1 증가
					if(list.get(j).number==recommand) {
						list.get(j).total+=1;
						break;
					}
				}
			}
			// 추천한 학생이 액자에 걸려있지 않은 경우
			else {
				// 액자가 이미 다 차있는 경우 추천횟수가 가장 적은 학생 삭제후 추천 학생 삽입
				if(list.size()>=n) {
					Collections.sort(list); // 정렬
					int remove=list.get(0).number;  // 추천횟수가 가장 적은 학생 번호
					student[remove]=0; // 해당 학생의 총 추천 횟수 초기화
					list.remove(0); // 리스트에서 삭제
				}
				// 추천 받은 학생의 번호, 추천횟수 1, 추천 받은 시간 i 삽입
				list.add(new Student_1713(recommand,1,i)); 
				student[recommand]=1;
			}
		}
		
		// 추천 횟수가 0이 아닌 사람이 최종 후보
		for(int i=0;i<101;i++) {
			if(student[i]!=0)
				System.out.print(i+" ");
		}
	}
}

 

[고찰]

 이번 문제는 시뮬레이션 유형으로 주어진 조건을 모두 구현하는 문제이다. 시뮬레이션 문제는 어려운 알고리즘을 사용해야 하는 문제는 아니지만 구현해야 하는 조건이 많아 그만큼 코드 길이도 길어져 어렵게 느껴지는 문제이다. 이럴때는 문제를 구조화하는 것이 중요하다. 먼저, 후보의 사진을 게시할 수 있는 규칙은

 

① N개의 사진틀 중, 비어있는 사진 틀이 존재한다면 학생 사진 게시

② 비어있는 사진 틀이 존재하지 않는다면

   ③ 추천 받은 횟수가 가장 적은 학생 사진 삭제 후 추천 학생 사진 게시

   ④ 추천 받은 횟수가 같으면 게시된 지 가장 오래된 사진 삭제 후 추천 학생 사진 게시

단, ⑤ 현재 사진이 게시된 학생이 추천을 받은 경우에는 횟수 증가

로 정리할 수 있다. 이렇게 문제를 구조화 하였다면 차근차근 구현해나가면 된다. 

 

 우선 각 학생별 번호, 총 추천횟수, 등록된 시간을 저장하는 클래스를 선언하고, ③ 클래스 내에서 총 추천 횟수를 기준으로 정렬해주는 함수를 구현하는 것이 효율적이다. ④ 이때 총 추천 횟수가 같다면 등록된 시간으로 정렬해준다. 즉, 이 클래스는 액자에 걸린 학생들의 정보를 저장하는 용도이다. 

 이후 m번 추천 학생을 입력 받아 조건들을 처리해주어햐 한다. 매번 연결리스트에 저장된 액자에 걸린 학생들을 탐색하는 것은 번거롭기 때문에 학생들의 총 추천횟수만 저장하는 배열을 선언하는 것이 편리하다. ⑤ 입력된 추천 학생의 추천 횟수가 0이 아니라면 해당 학생은 이미 액자에 걸린 학생이기 때문에 배열과, 연결리스트에 저장된 클래스에 해당 학생의 번호를 찾아 총 추천 횟수를 저장한다. 

 입력된 추천 학생의 추천 횟수가 0이라면 액자에 걸리지 않은 학생이기 때문에 ② 연결리스트의 크기가 걸 수 있는 액자의 개수인 n 이상이라면 연결리스트를 정렬하여 가장 앞에 있는 학생을 삭제하고 추천 받은 학생을 삽입해준다. 

 

시뮬레이션 문제는 삼성 SW 역량테스트에 많이 출제되기 때문에 이렇게 구현 능력을 기를 수 있는 시뮬레이션 문제들을 더 많이 풀어봐야겠다.