[백준] 2461. 대표 선수 (Java)

 

🔒 문제

2461번: 대표 선수

 

 

🔑 알고리즘

투 포인터

 

 

💡  풀이

대표 학생을 선택하는 모든 경우의 수는

M^N 이고 N과 M 모두 최대 1000 이기 때문에 시간 초과가 발생할 것이다.

 

따라서 각 학급마다 모든 학생들을 능력치 순으로 정렬하고,

각 학급의 후보 학생의 최소값을 

각 학급마다 현재 뽑힌 학생들과 능력치가 유사한 학생의 포인터를 두어 비교하는 방법을 사용하였다.

해당 방법을 사용하면 이미 지나간 학생들(능력치가 낮은 학생들)의 중복 확인을 막을 수 있어 시간이 단축된다.

 

예제 입력을 예로 들면

1. 각 학급의 학생 능력치순으로 정렬

가장 능력치가 낮은 학생들(후보 학생)의 능력치 차이 저장 (14- 7 = 7)

12	16	43	67
7	17	48	68
14	15	54	77

 

2. 후보 학생 중 능력치가 가장 낮은 학생을 후보에서 제거하고 다음 학생을 후보에 삽입

12	16	43	67
	17	48	68
14	15	54	77

3. 새로운 학생을 넣었을 경우의 능력치 차이 비교 및 갱신 (17-12 = 5)

 

4. 모든 학급의 학생을 다 비교할 때까지 반복 

	16	43	67
	17	48	68
14	15	54	77

17-14= 3

 

	16	43	67
	17	48	68
	15	54	77

17-15= 2

 

...

 

			67
			68
			77

77 - 67 = 10

 

 

모든 학급의 인덱스가 마지막 값이라면 종료하고

최소값을 출력한다.

 

 

 

✏️ 코드

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

public class Main {
	static int N, M, arr[][], index[];

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		arr = new int[N][M];
		index = new int[N];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < M; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		for (int i = 0; i < N; i++)
			Arrays.sort(arr[i]);

		int minDiff = getDiff();
		while (true) {
			if (!setNext())
				break;

			int curDiff = getDiff();
			if (curDiff < minDiff)
				minDiff = curDiff;
		}

		System.out.println(minDiff);
	}

	private static boolean setNext() {

		int min = Integer.MAX_VALUE;
		int minIndex = -1;

		for (int i = 0; i < N; i++) {

			if (index[i] == M - 1)
				continue;

			int value = arr[i][index[i]];

			if (value < min) {
				min = value;
				minIndex = i;
			}
		}

		if (minIndex == -1)
			return false;

		index[minIndex]++;
		return true;
	}

	static int getDiff() {

		int max = Integer.MIN_VALUE;
		int min = Integer.MAX_VALUE;

		for (int i = 0; i < N; i++) {
			int value = arr[i][index[i]];

			if (value > max)
				max = value;
			if (value < min)
				min = value;
		}

		return max - min;
	}

}