[백준/1713]java.후보추천하기

남순식·2022년 12월 13일
0
post-thumbnail

문제를 보자.

후보를 일정기간동안 추천에 의하여 정해진 수만큼만 선정한다고 한다.

정해진 수만큼 후보들의 사진을 걸기위해 사진틀을 미리 만들어놨다고 하고,

시작하기전엔 모두 비어있으나 특정학생을 추천하면 반드시 사진틀에 게시돼야한다.

비어있는 틀이 없을경우 현재까지의 추천수가 가장적은 후보를 삭제하고 받았던 표는 0개가 된다. 그후 새로운 후보를 추가한다.

이때 현재까지 받은 추천이 가장적은학생이 두 명 이상일경우에는 오래게시됐던 후보를 삭제시킨다.

만일 후보에 이미 올라있는 학생을 추천할시에는 받은득표수만 +1이 된다.

예제 입,출력 을 보면
사진틀 3
총 추천횟수 9
2 1 4 3 5 6 2 7 2는 각각 추천하는 특정학생의 번호이다.

따라서
계속 1표씩 들어오니
2,1,4,3,5까지는 삭제되고
6(1),2(2),7(1) 이된다.
후보를 오름차순으로 정렬한다고 했으니
따라서 출력은 2,6,7이 되겠다.

힌트는 비교할 것이 여러개라는 것이다.

투표회수가 가장적은 사람이 삭제되는 경우에 투표회수를 기록해서 비교해야하고
가장적은 사람이 두명 이상 있을시 오래된 사람을 삭제해야하는 경우엔
후보안에서 후보에추가된 순서를 비교해야한다.

이전에 글을 썼던
Comparable을 사용한다면 될것이다.
클래스를 만들고, 그클래스를 이용한 객체들을 생성하여
자기자신객체와 매개변수객체를 비교한다면 나의 투표수와, 매개변수의투표수를 비교할 수 있고
투표수가 같을땐 오래된 순서로 비교할 수 있다.

Comparable을 모른다면 Comparable에 관한글을 읽고 오면 좋겠다.

따라서
내가만들 클래스는 이렇게 만들면 될것이다.

class voteNum {
    int idx, key, val;
    voteNum (int idx, int key, int val){
    this.idx = idx;               		//들어온 순서
    this.key = key;           			//해당특정학생 번호
    this.val = val;						//득표수
}

이것을 가지고 비교해야한다면?

static class voteNum implements Comparable<voteNum>{
    int idx, key, val;
    voteNum (int idx, int key, int val){
    this.idx = idx;
    this.key = key;
    this.val = val;
    }

    @Override
    public int compareTo(voteNum o) {
        if (this.val == o.val){
            return this.idx - o.idx;
        } else {
            return this.val - o.val;
        }
    }
}

이렇게한다면 오름차순정렬도 쉽게 할 수있다.
맨앞은 투표수가 적은 학생이 올것이고, 두명이상이라면 더 오래된 순서로 정렬 될것이다.
이것만 구현할 수 있다면 문제는 해결할 수 있다.

풀이를 보도록 하자

class Main {
    static class voteNum implements Comparable<voteNum>{
        int idx, key, val;
        voteNum (int idx, int key, int val){
            this.idx = idx;
            this.key = key;
            this.val = val;
        }

        @Override
        public int compareTo(voteNum o) {
            if (this.val == o.val){
                return this.idx - o.idx;
            } else {
                return this.val - o.val;
            }
        }
    }
    static int N, M;
    static Scanner sc;
    static ArrayList<voteNum> list;
    static ArrayList<Integer> result;
    static boolean flag;

    public static void main(String[] args) {

        sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        list = new ArrayList<>();
        result = new ArrayList<>();

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < M; i++) {
            int x = sc.nextInt();
            if (list.size() < N) {
                flag = false;
                for (int j = 0; j < list.size(); j++) {
                    if (list.get(j).key == x){
                        list.get(j).val++;
                        flag = true;
                        break;
                    }
                }
                if (!flag){
                    list.add(new voteNum(i,x,1));
                }
            } else {
                Collections.sort(list);
                flag = false;
                for (int j = 0; j < list.size(); j++) {
                    if (list.get(j).key == x){
                        list.get(j).val++;
                        flag = true;
                        break;
                    }
                }
                if (!flag){
                    list.remove(0);
                    list.add(new voteNum(i,x,1));
                }
            }
        }
        for (int i = 0; i < list.size(); i++) {
            result.add(list.get(i).key);
        }
        Collections.sort(result);
        for (int i = 0; i < result.size(); i++) {
            sb.append(result.get(i) + " ");
        }
        System.out.println(sb);
    }
}

추가 설명으로
boolean 타입 flag는 지금 추천하는학생이 이미 후보안에 있는것인지 체크하기 위함이고, 체크했을때 후보안에 있다면 true를 뱉고 반복문이 끝난다.
만일 후보에 없다면 그대로 false 일테고 후보에 없는사람을 추천했을시에는
후보가 새로 한명 올라가야한다.
만약 사이즈가 N일때는
기존에있던 제일작은득표수를 받은후보, 또는 오래된 후보를 삭제하고 후보로 올려야 한다.

사이즈가 N 미만일때는 정렬을 해줄 필요가 없지만,
그이상이면 list를 내가 정한 기준으로 정렬하여 새로 후보가 올라올때는
list.remove(0); 을 해주면 된다

마지막으로 StringBuilder 를 사용하는 이유는
반복문안에서 System.out.print를 사용하면
수행시간이 길어져서
한번에 출력하기위해 사용하였다.

profile
java 주니어

0개의 댓글