[JAVA] 백준 1713번: 후보 추천하기

<문제>

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

1713번: 후보 추천하기

<풀이>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class P1713 {
	static int photo[]; //사진 틀
	static int number[]; //추천 학생 번호를 저장하는 배열 
	static int recommend[]; //추천 받은 횟수를 저장하는 배열
	static int updated[]; //가장 오래 게시되어있던 사진을 찾기 위한 배열 (숫자가 작을수록 오래됐다는 뜻)
	static int updateNum=1; //업데이트 번호 
	
	static void post(int num) {
		boolean isPosted=false;
		int index=-1;
		
		for(int i=0;i<photo.length;i++) {
			if(photo[i]==num) { //이미 사진이 게시되어 있음
				recommend[num]++; //해당 번호를 가진 학생의 추천횟수 증가 
				isPosted=true; // 사진 게시됨
			}
		}
		
		if(!isPosted) { // 게시되지 않은 경우
			for(int i=0;i<photo.length;i++) {
				if(photo[i]==0) { // 사진 비어있는 곳이 있으면
					index=i; //인덱스 저장
					break;
				}
			}
			if(index==-1) { //사진 칸이 꽉 차 있는 경우 
				int deletedIndex=counting(photo); //추천 횟수를 확인하는 함수 실행 
				photo[deletedIndex]=num;
			}
			else { //사진 칸이 비어있는 곳이 있는 경우
				photo[index]=num;
			}
			recommend[num]++;
			updated[num]=updateNum;
			updateNum++;
		}
	}
	static int counting(int arr[]) { //추천 횟수를 확인하는 함수 
		int min=Integer.MAX_VALUE;
		int oldest=Integer.MAX_VALUE;
		int count=0;
		int index=0;
		
		//추천횟수가 가장 작은 값을 찾음
		for(int i=0;i<arr.length;i++) {
			min=Math.min(min, recommend[arr[i]]); //min => 추천 횟수가 가장 작은 값
		}
		//추천 받은 횟수가 적은 사람의 수를 셈
		for(int i=0;i<arr.length;i++) {
			if(recommend[arr[i]]==min)
				count++;
		}
		
		if(count>=2) { //추천 받은 횟수가 적은 사람이 2명 이상
			for(int i=0;i<arr.length;i++) {
				if(recommend[arr[i]]==min)//추천횟수가 min값과 같은 사람 중에, 가장 오래된 사람을 찾아야함 !!
					oldest=Math.min(oldest,updated[arr[i]]); //제일 값이 작은 값을 찾음 => 가장 오래 게시되어있던
			}
			
			for(int i=0;i<arr.length;i++) {
				if(updated[arr[i]]==oldest) { // 가장 오래 게시되어있던 사람을 
					recommend[arr[i]]=0; //추천 받은 횟수 0으로 변경 => 삭제 
					index=i; //해당 인덱스 저장
				}
			}
		}
		else { //추천 받은 횟수가 적은 사람이 1명 
			for(int i=0;i<arr.length;i++) {
				if(recommend[arr[i]]==min) {
					recommend[arr[i]]=0; //추천 받은 횟수 0으로 변경 => 삭제 
					index=i; //해당 인덱스 저장 
				}
			}
		}
		return index;
	}
	//후보 추천하기
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n=Integer.parseInt(br.readLine()); //사진 틀의 개수 
		int count=Integer.parseInt(br.readLine()); //전체 학생의 총 추천 횟수 
		
		photo=new int[n];
		number=new int[count];
		recommend=new int[101]; 
		updated=new int[101];
		
		StringTokenizer st=new StringTokenizer(br.readLine());
		for(int i=0;i<count;i++) {
			number[i]=Integer.parseInt(st.nextToken()); //추천 학생 번호 저장
		}
		for(int i=0;i<number.length;i++) {
			post(number[i]);
		}
		Arrays.sort(photo);
		for(int i=0;i<photo.length;i++) {
			if(photo[i]!=0) //사진 틀의 개수가 후보자 수보다 많으면 0이 나올 수 있으므로 고려해줘야함
				System.out.print(photo[i]+" ");
		}
	
	}

}

 

 

✏️ 풀이 방법

1. 사진이 이미 게시되어 있는지 확인

   1-1. 게시되어 있다면

         :  해당 번호를 가진 학생의 추천 횟수 증가

   1-2. 게시되어 있지 않다면

       ① 사진 틀이 빈 곳이 있는 경우

         : 해당 틀에 학생의 사진 게시, 해당 학생의 업데이트 번호 넣기, 업데이트 번호 증가 

       ② 사진 틀이 빈 곳이 없는 경우

         : 추천 횟수를 확인하는 함수(counting) 실행 

            -> 틀에 게시돼 있는 각 학생들의 추천 횟수 확인

              ① 추천 받은 횟수가 적은 학생이 1명이면 

               : 해당 학생의 추천 횟수를 0으로 변경, 그 인덱스를 저장하여 새로운 학생의 사진 게시 

              ② 추천 받은 횟수가 적은 학생이 2명 이상이면

                : 추천 횟수가 가장 적은 학생들 중에 가장 오래 게시돼 있던 학생의 추천 횟수를 0으로 변경,

                  그 인덱스를 저장하여 새로운 학생의 사진 게시 

             -> 새로 게시된 학생의 추천 횟수 증가, 새로 게시된 학생에게 업데이트 번호 부여, 업데이트 번호 증가 

2. 최종 후보를 오름차순으로 출력

 

❗ 주의해야 할 점

사진 틀의 개수가 추천 횟수보다 많을 경우도 고려해줘야한다.

이 경우를 생각을 못해서 계속 삽질했다 🥹 

 

ex) 사진 틀의 개수 = 4, 추천 횟수 =3 , 입력 받은 번호 = 1,2,3 일 때 

이 경우를 고려해주지 않으면, 내 코드의 경우는 0 1 2 3 이라는 수가 출력된다. 0이 출력되게 되면 틀린다 ! 

 

❗반례 정리 (출처: 백준 질문게시판)

Input:
2
6
2 1 1 2 3 3
Answer:
1 3

Input:
3
12
1 5 1 1 7 5 9 9 9 5 4 6
Answer:
5 6 9

 

Input:

3

11

1 1 1 2 1 3 3 2 3 2 4 

Answer:
1 3 4

 

✍🏻 느낀점

 너무 자잘자잘한 실수들을 많이 한 문제였다. 우선, 조건들이 너무 많아서 조건을 생각하고 정리하는게 헷갈렸고,

이미 사진이 게시돼 있는 경우에 해당 번호 학생의 추천 횟수만 증가시키는 것이 아니라, 업데이트 번호도 증가시켜서 꼬이고

추천 횟수가 가장 적은 min 값을 구하기 위해 초기화를 int min=recommend[arr[0]] 이렇게 고정해놓아서 틀리고,,

그리고 추천 횟수가 적은 사람들 중에 가장 사진이 오래 게시돼 있던 학생을 찾아야하는데, 이 조건을 해주지 않아서 틀렸다 ㅠ.ㅠ

 

 여기까지 고쳤을 때 백준 질문 게시판에 나와있는 모든 반례가 맞았는데도 계속 틀렸다 틀렸다 나왔는데, 우연히 다른 블로그를 통해

저 위의 경우를 찾아서 4번만에 맞았다 ,, 이런 문제 나왔을 때는 바로 코딩하려고 하지 말고, 꼭 조건을 분기해서 생각해봐야겠다.

좀 더 꼼꼼해져야겠다. 그리고 나는 문제를 너무 더럽게(?) 푼 것 같아서 깔끔하게 푸는 연습을 해야겠다.