반응형

1417번 국회의원 선거

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

 

1417번: 국회의원 선거

첫째 줄에 후보의 수 N이 주어진다. 둘째 줄부터 차례대로 기호 1번을 찍으려고 하는 사람의 수, 기호 2번을 찍으려고 하는 수, 이렇게 총 N개의 줄에 걸쳐 입력이 들어온다. N은 50보다 작거나 같

www.acmicpc.net

Comment

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

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

hint

우선순위 큐를 활용했다.

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

Solution

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
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++;
 
    }
}
 
cs
 
반응형
저작자표시 비영리 변경금지

'공부 > Algorithm' 카테고리의 다른 글

백준 14494번 다이나믹이 뭐예요? 자바로 풀어 본 짧은 글  (0) 2023.09.15
백준 1680번 쓰레기 수거 자바로 풀어 본 짧은 글  (0) 2023.09.07
백준 골드5 달성!  (0) 2023.08.11
백준 2644번 촌수 계산 자바(BFS,DFS)로 풀어 본 짧은 글  (0) 2023.08.03
백준 2023번 신기한 소수 자바로 풀어 본 짧은 글  (0) 2023.07.25

+ Recent posts

티스토리툴바