[Java] SW Expert Academy 1204번 문제: [S/W 문제해결 기본] 1일차 - 최빈수 구하기 (PriorityQueue, 우선순위큐)

--- 문제 ---

• [S/W 문제해결 기본] 1일차 - 최빈수 구하기
  
  • 핵심 알고리즘 : PriorityQueue, 우선순위큐 (Max Heap)

--- 코드 ---

 

1. 점수 input을 받으면면, 동시에 0~100개의 배열 scores에서 해당 점수 자리에 +1을 한다.

2. +1을 한 수가 저장된 max값과 같으면 ? Max heap 즉, PriorityQueue에 해당 점수를 추가
    +1을 한 수가 기존 max보다 크면? 기존 PriorityQueue의 값을 모두 지우고 해당 점수를 추가

3. 이 과정을 반복하고 점수를 다 받으면 PriorityQueue에서 제일 첫 우선순위 값을 출력 (저장된 수 중에서 가장 큰 값)

 

(단, 최빈수가 여러 개 일 때에는 가장 큰 점수를 출력하라).

라는 조건이 있기 때문에 PriorityQueue 자료구조를 사용하였다.

해당 자료 구조는 가장 우선 순위가 높은 값을 제일 head에 두는 자료 구조 이기 때문에,
최빈수의 값이 여러 개일 때 그중 가장 큰 값을 빠르게 찾아내기 위해 사용하였다.

 

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Sw1204 {

	public static void main(String[] args) throws FileNotFoundException {
    
		System.setIn(new FileInputStream("./src/1204.txt"));

		Scanner sc = new Scanner(System.in);
		
		int T=sc.nextInt();
		
		for(int test_case = 1; test_case <= T; test_case++) {
			
			int max = 0 ;
			PriorityQueue<Integer> max_poses = 
					new PriorityQueue<>(Collections.reverseOrder());
			sc.nextInt();
			int[] scores = new int[101];
			
			for(int i=0; i<1000; ++i) {
				int score = sc.nextInt();
				scores[score] += 1;
				if(scores[score]==max) {
					max_poses.add(score);
				}
				else if(scores[score]>max) {
					max = scores[score];
					max_poses.clear();
					max_poses.add(score);
				}
			}
			System.out.printf("#%d %d%n",test_case,max_poses.poll());
			
		}
	}

}

 

--- 출처 ---

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV13zo1KAAACFAYh&categoryId=AV13zo1KAAACFAYh&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy