백준 2461: 대표 선수 [Java]

문제 바로 가기

아이디어

각 반에서 대표로 선발된 학생들의 능력치의 차이가 최소가 되도록 해야 하는 문제다.
능력 순으로 정렬하는 우선순위 큐와 반별로 갱신되는 능력값 배열을 사용하여 풀었다.

1. 우선순위 큐에 능력과 반 정보를 저장한다.
2. 한 명씩 우선순위 큐에서 뽑는다.
3. 해당하는 반의 능력값을 갱신한다.
4. 만약 모든 반의 능력값이 갱신되어있다면 최댓값과 최솟값의 차이를 구한다.

풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	static class Student implements Comparable<Student> {
		int classNumber, skill;

		public Student(int classNumber, int skill) {
			this.classNumber = classNumber;
			this.skill = skill;
		}

		@Override
		public int compareTo(Student o) {
			return this.skill - o.skill;
		}
	}

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static PriorityQueue<Student> pq;
	static int N, M, presentCount;
	static int[] classSkill;
	static boolean[] isNotPresent;

	public static void main(String[] args) throws IOException {
		init();
		solve();
	}

	private static void solve() {
		int answer = 1_000_000_000;

		while (!pq.isEmpty()) {
			Student current = pq.poll();
			int classNumber = current.classNumber;
			int skill = current.skill;

			if (isNotPresent[current.classNumber]) {
				isNotPresent[current.classNumber] = false;
				presentCount++;
			}
			classSkill[classNumber] = skill;

			if (presentCount == N) {
				int min = 1_000_000_000;
				int max = 0;
				for (int i = 1; i <= N; i++) {
					int value = classSkill[i];
					min = Math.min(min, value);
					max = Math.max(max, value);
				}
				answer = Math.min(answer, max - min);
			}
		}

		System.out.println(answer);
	}

	private static void init() throws IOException {
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		isNotPresent = new boolean[N + 1];
		classSkill = new int[N + 1];
		pq = new PriorityQueue<>();
		presentCount = 0;

		Arrays.fill(isNotPresent, true);
		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());

			for (int j = 0; j < M; j++) {
				pq.add(new Student(i, Integer.parseInt(st.nextToken())));
			}
		}
	}
}

N이 1000 이하라서 가능한 풀이라고 생각한다. 정답을 갱신하는 부분을 더 효율 좋게 할 수 있을것 같다고 생각했다. 아래는 최댓값 PQ와 최솟갑 PQ를 사용하여 정답을 갱신하는 코드다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	static class Student implements Comparable<Student> {
		int classNumber, skill;

		public Student(int classNumber, int skill) {
			this.classNumber = classNumber;
			this.skill = skill;
		}

		@Override
		public int compareTo(Student o) {
			return this.skill - o.skill; // 오름차순
		}
	}

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static PriorityQueue<Student> pq;
	static PriorityQueue<Student> minPQ;
	static PriorityQueue<Student> maxPQ;
	static int N, M, presentCount;
	static int[] classSkill;
	static boolean[] isNotPresent;

	public static void main(String[] args) throws IOException {
		init();
		solve();
	}

	private static void solve() {
		int answer = 1_000_000_000;

		while (!pq.isEmpty()) {
			Student current = pq.poll();
			int classNumber = current.classNumber;
			int skill = current.skill;

			if (isNotPresent[classNumber]) {
				isNotPresent[classNumber] = false;
				presentCount++;
			}

			classSkill[classNumber] = skill;
			minPQ.add(new Student(classNumber, skill));
			maxPQ.add(new Student(classNumber, skill));

			if (presentCount == N) {
				while (!minPQ.isEmpty() && classSkill[minPQ.peek().classNumber] != minPQ.peek().skill) {
					minPQ.poll();
				}
				while (!maxPQ.isEmpty() && classSkill[maxPQ.peek().classNumber] != maxPQ.peek().skill) {
					maxPQ.poll();
				}

				int min = minPQ.peek().skill;
				int max = maxPQ.peek().skill;
				answer = Math.min(answer, max - min);
			}
		}

		System.out.println(answer);
	}

	private static void init() throws IOException {
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		isNotPresent = new boolean[N + 1];
		classSkill = new int[N + 1];
		pq = new PriorityQueue<>();
		minPQ = new PriorityQueue<>((a, b) -> a.skill - b.skill);
		maxPQ = new PriorityQueue<>((a, b) -> b.skill - a.skill);

		presentCount = 0;
		Arrays.fill(isNotPresent, true);

		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				pq.add(new Student(i, Integer.parseInt(st.nextToken())));
			}
		}
	}
}

막상 해보긴 했는데, 코드도 더 길어지면서 복잡하고 시간도 별로 차이나지 않아서 아쉬웠다.