[Baekjoon] 11637_인기 투표

Silver V

문제(출처: https://www.acmicpc.net/problem/11637)

---

< 인기 투표 >

 

문제 풀이 

 

우선순위 큐에 R과 투표수를 저장한다. 투표수가 많은 순서대로 정렬하여 투표 수가 2명 이상 같다면 "no winner"를 출력한다. 2명 이상 같지 않다면 과반수인지 절반 이하인지 확인 후 출력한다.

 

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Comparator;
import java.util.PriorityQueue;

public class _11637_ { // 인기 투표

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

		int t = Integer.parseInt(bf.readLine());

		PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				return o2[1] - o1[1];
			}

		});

		for (int i = 0; i < t; i++) {
			int n = Integer.parseInt(bf.readLine());
			int sum = 0;
			for (int k = 0; k < n; k++) {
				int x = Integer.parseInt(bf.readLine());
				sum += x;
				queue.add(new int[] { k + 1, x });
			}
			int temp[] = queue.poll();
			if (temp[1] == queue.peek()[1]) {
				bw.write("no winner \n");
			} else {
				if (temp[1] > sum / 2)
					bw.write("majority winner " + temp[0] + "\n");
				else
					bw.write("minority winner " + temp[0] + "\n");
			}
			queue.clear();
		}
		bw.flush();
	}
}

 

Main

변수)
t : 테스트 케이스 수
queue : 우선순위 큐 <후보자 번호, 득표 수>
n : 후보자 수
sum : 총 득표 수

 

- 테스트 케이스 수(t) 입력

- 테스트 케이스 수(t) 만큼 반복

: 후보자 수(n) 입력

: 후보자 수만큼 후보자의 득표 수를 입력받아 queue에 저장 및 총 득표 수에 합

: queue에서 뽑은 것과 다음 queue 값의 득표 수가 같다면 최다 득표자가 없는 것이므로 "no winner" 출력

: 같지 않다면 총 득표 수의 절반이 넘는지 확인 후 넘으면 "majority winner" 출력, 절반이 넘지 않으면 "minority winner" 출력

---

---