백준 1417번 국회의원 선거 자바로 풀어 본 짧은 글

1417번 국회의원 선거

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

1417번: 국회의원 선거

---

Comment

자료구조를 활용하는 문제중에서 난이도가 쉬웠기에 여러가지 시도해보기 좋았던 문제같다.

처음엔 그냥 자료구조 클래스만 활용할까 하다가 객체도 같이 써보면 재밌지 않을까 해서 같이 사용해봤다

---

hint

우선순위 큐를 활용했다.

객체를 사용한다면 해당 객체에 Comparable를 상속받아야함

---

Solution

전체 입력값 자체가 적어서 시간은 볼 필요 없긴 할듯하다

우선순위 큐를 써봤는데 객체에서는 자동정렬을 계속 해주지 않는건지 처음 입력된 우선순위 큐 객체에서만 투표수를 가져가고 있었다. 때문에 이를 해결하기 위해 우선순위 큐에서 득표 수에 변경이 있을 때마다 큐에서 꺼냈다가 다시 넣어주는 형식으로 반복을 했다.

그래도 객체를 기준으로 우선순위 큐를 다루는게 은근 재밌었던 문제

import java.io.*;
import java.util.PriorityQueue;
import java.util.Queue;
 
public class p1417 {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int count = 0;
        int n = Integer.parseInt(br.readLine());
        Queue<Candidate> candiQ = new PriorityQueue<>(n+8);
 
        Candidate dasom = new Candidate(1, Integer.parseInt(br.readLine()));
 
        for(int i = 2; i < n+1;i++){
            int receveVote = Integer.parseInt(br.readLine());
            candiQ.offer(new Candidate(i, receveVote));
        }
 
        if(candiQ.isEmpty()){
            System.out.println(0);
            return;
        }
 
        //기호1번을 1등으로
        while (dasom.getReceveVote() <= candiQ.peek().getReceveVote()){
            candiQ.peek().voteControl(0);
            Candidate temp = candiQ.poll();
            candiQ.offer(temp);
            dasom.voteControl(1);
            count++;
        }
 
        System.out.println(count);
    }
}
 
 
/**
 * 후보자번호, 받은 득표수가 들어있는 후보객체
 * 우선순위큐를 위해 Comparable을 상속받음
 */
class Candidate implements Comparable<Candidate>{
    private final int number;
 
    private int receveVote = 0;
 
    Candidate(int number) {
        this.number = number;
    }
 
    Candidate(int number, int receveVote) {
        this.number = number;
        this.receveVote = receveVote;
    }
 
    @Override
    public int compareTo(Candidate o) {
        //receveVote 내림차순정렬
        return o.receveVote - receveVote;
    }
 
    public int getReceveVote() {
        return receveVote;
    }
 
    public int getNumber() {
        return number;
    }
 
    public void voteControl(int mode){
        if(mode == 0){
            receveVote--;
            return;
        }
        receveVote++;
 
    }
}