[BOJ] 백준 1713 - 후보 추천하기 풀이

1. 문제

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

1713번: 후보 추천하기

 

 

2. 풀이

시뮬레이션 문제로 시나리오 그대로 코드를 작성하면 된다.

우선 예제 입력 1에서 3번째 줄을 살펴보자. 3번째 줄 입력은 추천 받은 학생을 나타내는 번호가 빈칸을 사이에 두고 있다.
그렇다면 사진틀을 하나의 객체 참조 변수로 본다면 안에 들어가는 인스턴스는 어떻게 될까? 바로 추천 받은 학생, 추천수이다.
그래서 static class로 추천 받은 학생의 이름과 추천 수를 필드로 갖는 클래스를 만들었다.
그 후 frame이라는 List를 만들고, 입력 받을 각각의 변수와 배열을 선언했다.

이제 로직을 살펴보자.
로직에서는 경우의 수가 크게 3단계로 나누어져 있다.

(1) frame 리스트가 비어있을 때
(2) frame 리스트의 사이즈가 N개 미만일 때
(3) frame 리스트의 사이즈가 N개 일 때 

(1) frame 리스트가 비어있을 때.
- 리스트가 비어 있으므로 무조건 사진틀에 사진이 걸린다. static class로 선언된 Info 객체를 만들고 그 안에 있는 추천수(recomm_cnt)를 하나 증가시켜서 frame 리스트에 넣어준다.

(2) frame 리스트의 사이즈가 N개 미만일 때.
- 리스트의 사이즈가 N가 미만이거나 N개 일 때 모두 현재 추천 받은 사람이 사진 틀에 걸려 있는 사람 중 하나 인지 검증이 필요하다.

- 그래서 else if 에서 N보다 작거나 같다로 분기(44줄)를 나눴고, plusRecommend()를 실행하여 현재 추천 받은 사람이 사진틀에 걸려있다면 그 사람의 추천수를 하나 증가시키고 flag 변수를 false로 바꾼다. 

- flag 변수가 false라는 것은 현재 추천 받은 학생이 사진 틀에 없다는 이야기이므로 사진 틀에 추가한다.

(3) frame 리스트의 사이즈가 N개 일 때.
- frame 리스트의 사이즈가 N개 미만일 때와 마찬가지로 현재 추천 받은 사람이 사진 틀에 걸려 있는 사람 중에 있는지 검증하는 plusRecommend()를 실행하고, flag 변수가 false라면 52줄 로직을 실행한다.

- 52줄 로직은 남은 사진 틀이 없고 새로운 사람이 추천 받았을 때를 의미한다. 문제에서 비어있는 사진 틀이 없을 경우 현재까지 받은 추천 받은 횟수가 가장 적은 사진을 제거하고 그 자리에 새로운 사진을 추가한다고 한다. 또 추천 수가 가장 적은 사진이 2개 이상이라면 그 중 오래된 사진을 제거한다.

- 그러나 이 코드에서는 제거한 자리에 새로운 사진을 추가하는 로직과 2개 이상일 때를 비교하는 로직이 따로 존재하지 않는다.

- 그 이유는 사진 틀을 담는 리스트가 ArrayList이기 때문이다.

- ArrayList는 add()를 호출하면 인덱스 순서대로 값을 채워넣는다. 이 말은 ArrayList에 들어가 있는 순서가 걸려 있는 사진의 시간 순서라는 것이다.

- 56번 줄을 보면 현재 담겨 있는 사진 틀을 하나씩 탐색하면서 min 변수에 추천 수의 최소 값을 갱신해주고 있다. 갱신할 때는 그 위치를 idx 변수에 넣어 보관한다. 사진 틀 리스트를 한 바퀴를 돌려 추천수의 최소 값을 찾으면 그 위치의 사진틀을 제거하고 현재 추천 받은 사람의 추천수를 하나 증가시켜 리스트에 넣으면 된다.

- frame 틀 안의 객체의 순서는 걸려 있는 사진의 시간 순서이기 때문에, 만약 최소 값이 2개 이상이 나온다고 해도 그 중 처음으로 최소 값이 나온 idx를 보관하고 있다면 다른 것들은 삭제 대상이 아니다.

- 그리고 로직을 한번 마치고 나면 flag를 다시 false로 돌려놔야 한다.

마지막으로 사진 틀에 걸려 있는 추천 받은 사람을 정렬하여 출력하면 정답이다!

 

3. 소스 코드

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

class Main {
    static class Info {
        public int student_name; // 학생의 이름
        public int recomm_cnt = 0; // 특정 학생의 추천수

        public Info(int student_name) {
            this.student_name = student_name;
        }
    }

    static boolean flag = false;
    static int[] recommend;
    static List<Info> frame = new ArrayList<>();

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

        int N = Integer.parseInt(br.readLine());  // 사진틀의 개수
        int student = Integer.parseInt(br.readLine()); // 학생들의 추천수

        recommend = new int[student];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < student; i++) {
            recommend[i] = Integer.parseInt(st.nextToken());
        }

        for (int i = 0; i < student; i++) {
            Info info = new Info(recommend[i]);

            if (frame.isEmpty()) {                     // 사진 틀이 비어있을 때
                info.recomm_cnt += 1;
                frame.add(info);
            }

            else if (frame.size() <= N) {
                plusRecommend(i);

                if (!flag && frame.size() < N) {       // 추천 받은 학생이 프레임에 없을 경우
                    info.recomm_cnt += 1;
                    frame.add(info);
                }

                else if (!flag && frame.size() == N) {
                    int idx = 0;
                    int min = Integer.MAX_VALUE;

                    for (int k = 0; k < frame.size(); k++) {   // 남은 프레임이 없고 새로운 사람이 추천 받았을 떄.
                        if (frame.get(k).recomm_cnt < min) {
                            min = frame.get(k).recomm_cnt;
                            idx = k;
                        }
                    }

                    frame.remove(idx);
                    info.recomm_cnt += 1;
                    frame.add(info);
                }
            }
            flag = false;
        }

        List<Integer> out = new ArrayList<>();
        for (Info info : frame) {
            out.add(info.student_name);
        }

        Collections.sort(out);
        for (int i = 0; i < out.size(); i++) {
            bw.write(Integer.toString(out.get(i)) + " ");
        }

        bw.flush();
        bw.close();
        br.close();
    }

    static public void plusRecommend(int i) {              // 이미 있는 학생의 추천수를 하나 증가.
        for (int j = 0; j < frame.size(); j++) {
            if (frame.get(j).student_name == recommend[i]) {      
                frame.get(j).recomm_cnt += 1;

                flag = true;
                break;
            }
        }
    }
}