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

🌵 문제 분석

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

N개의 사진틀에 추천받은 학생의 사진이 게시된다. 총 S번 추천이 이루어진 후 최종 후보가 누군지 출력하라.

• 만약 자리가 없다면 추천 받은 횟수가 가장 적은(2명 이상이라면 추천받은지 더 오래된) 학생이 삭제되고, 그 자리에 게시된다. 
• 이미 게시된 학생이 또 추천받으면 추천횟수 증가, 사진틀에서 삭제되면 추천횟수는 0이 됨

입력 :

N (사진틀 개수)

S (총 추천 횟수)

S개의 학생 번호

🌵 구현 아이디어

💡 전체 동작 설계

• 사진틀을 List로 둔다.
• 학생을 Student 객체로 두고 변수로 학생 번호(id), 추천 받은 횟수(cnt), 게시된지 얼마나 지났는지 나타내는 값(time)을 둔다.
• 추천 받은 학생이 생기면 O(S)
  -> 추천 받은 학생이 사진 틀에 이미 있는지 확인한다. O(N)
  
  • 있으면 해당 학생의 추천받은 횟수(cnt)를 증가시킨다.
  • 없으면
    -> 사진틀이 꽉 찼는지 확인한다. O(1)
    • 꽉 참 
      • 추천 수가 가장 적은, 그 중에 가장 게시된지 오래된 학생을 찾아서 사진틀에서 제거한다. O(1)
      • 추천받은 학생의 Student 객체를 생성해서 새로 넣는다. O(1)
    • 자리 있음
      
      • Student객체를 생성해서 List에 저장한다. O(1)
  • 사진틀을 정렬한다. O(NlogN)
• S번의 추천이 끝났으면 사진틀에 게시된 학생의 번호(id)를 오름차순으로 출력한다. O(N)

🤔 사진틀이 꽉 찼을 때 삭제할 학생을 선정하는 방법은?

👉🏻 사진틀에 게시된 학생을 추천수(cnt)가 작은 순으로, 추천 수가 같을 경우 게시된 순서(time)가 오래된 순으로 정렬한다.

👉🏻 맨 앞에 있는 학생은 추천 수가 가장 작은 학생 중 게시된 순서가 가장 오래된 학생일 것이므로 사진틀 맨 앞의 학생을 삭제하면 된다.

🌵 시간 복잡도

• 추천 받은 학생 마다 아래를 반복 : O(S)
  • 추천 받은 학생이 사진틀에 이미 있는지 탐색 : O(N)
  • 사진 틀을 정렬 : O(NlogN)
  • 게시된 학생들의 번호를 오름차순으로 정렬 후 출력 : O(NlogN) + O(N)

S는 최대 1,000, N은 최대 20이므로

전체 시간 복잡도는 O(S) * (O(N)+O(NlogN)+O(NlogN)+O(N)) = 1,000 * (2*(20+20))=80,000

따라서 제한 시간(2초) 안에 연산 가능

🌵 알고리즘

구현

🌵 오답 노트

1. ans[] 크기를 N으로 설정해서 불필요한 0까지 출력하게 됨 

-> 크기를 frame.size()로 설정

반례 :

2
2
1

 

2. 추천받은 학생이 이미 frame에 있는 경우 그 학생의 추천수를 cnt++해주고 나서 frame을 정렬하지 않았음

-> frame을 정렬해줌

반례 :

3
8
1 1 1 1 2 2 3 3 4

 

3. line 39 부분에 break;가 빠지면 틀린 답이다.

왜냐하면 추천 횟수를 증가시키고 나서 바로 frame을 정렬하고 있는데

이때 순서가 바뀐 frame을 계속해서 순회하므로 이미 증가시킨 학생의 cnt를 또 증가시킬 수 있기 때문이다.

-> 따라서 break;를 꼭 넣어줘야 한다.

-> 또는 Collections.sort(frame)을 if(isExist) 하위에 포함시키면 된다.

//S개의 추천을 순회
for(int i=0; i<S; i++){
    boolean isExist = false;

    //이미 게시된 학생이면 추천 횟수 증가
    for(int j=0; j<frame.size(); j++){
        if(rec[i] == frame.get(j).id){
            frame.get(j).cnt += 1;
            isExist = true;
            Collections.sort(frame);
            break; //line 39
        }
    }

    //학생이 이미 게시되어 있다면 다음 추천으로 넘어감
    if(isExist) {
        continue;
    }

🌵 코드 설계

1. List<Stduent> frame 사진틀 선언
2. Student 객체 선언 후 id, cnt, time 변수 포함시키고 compareTo 구현 
3. int time = 1으로 초기화
4. int[] rec 추천받은 학생 S명 저장
5. rec를 순회하면서 아래 과정 반복
   1. 추천받은 학생이 있는지 나타내는 변수 boolean isExist 를 false로 선언
   2. 추천받은 학생 rec[i]이 frame에 있는지 확인
   3. 있다면 isExist = true로 만들고 해당 학생의 추천 횟수 cnt 증가
   4. 없다면 frame.size()==N인지 확인
      1. 맞다면 frame[0] 삭제
   5. new Student(i, 1, time)을 frame에 add
   6. time++
   7. frame을 정렬
6. frame을 Student.id순서 오름차순 정렬, 출력

🌵 정답 코드

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

public class Main {
    static int N, S;
    static List<Student> frame;
    static int time;
    static int[] rec;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        //N, S 입력받기
        N = Integer.parseInt(br.readLine());
        S = Integer.parseInt(br.readLine());

        //필요한 자료구조 선언
        frame = new ArrayList<>();
        time = 1;
        rec = new int[S];

        //추천받은 학생 S명 입력받기
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<S; i++){
            rec[i] = Integer.parseInt(st.nextToken());
        }

        //S개의 추천을 순회
        for(int i=0; i<S; i++){
            boolean isExist = false;

            //이미 게시된 학생이면 추천 횟수 증가
            for(int j=0; j<frame.size(); j++){
                if(rec[i] == frame.get(j).id){
                    frame.get(j).cnt += 1;
                    isExist = true;
                    Collections.sort(frame);
                    break;
                }
            }

            //학생이 이미 게시되어 있다면 다음 추천으로 넘어감
            if(isExist) {
                continue;
            }

            //frame이 꽉 찼다면 맨 앞 한명 삭제
            if(frame.size() == N){
                frame.remove(0);
            }

            //한 명 추가
            frame.add(new Student(rec[i], 1, time));
            time++;

            //frame 정렬
            Collections.sort(frame);
        }

        int[] ans = new int[frame.size()];
        for(int i=0; i<frame.size(); i++){
            ans[i] = frame.get(i).id;
        }
        Arrays.sort(ans);
        for(int tmp : ans)
            System.out.print(tmp + " ");


    }
}

class Student implements Comparable<Student>{
    int id, cnt, time; //학생번호, 추천받은 수, 프레임에 게시된 순서

    Student(int id, int cnt, int time){
        this.id = id;
        this.cnt = cnt;
        this.time = time;
    }

    @Override
    public int compareTo(Student o) {
        //cnt 오름차순 -> time 오름차순
        if(this.cnt == o.cnt){
            return this.time - o.time;
        }else return this.cnt - o.cnt;
    }
}