문제 링크
문제
티어: 골드 2
알고리즘: 정렬, 두 포인터
KOI 중학교에는 N개의 학급이 있으며, 각 학급의 학생 수는 모두 M명으로 구성된다. 이 중학교에서는 체육대회에 새로운 종목의 경기를 추가하였다. 이 경기에 대해 모든 학생들은 저마다의 능력을 나타내는 능력치를 가지고 있으며, 이 능력치는 모든 학생이 서로 다르다.
이 경기는 한반에서 한 명의 대표선수를 선발하여 치른다. 경기의 형평성을 위하여, 각각의 반에서 대표로 선발된 모든 학생들의 능력치 중 최댓값과 최솟값의 차이가 최소가 되도록 선수를 선발하려고 한다. 예를 들어, N=3, M=4인 경우 학생들의 능력치가 1반=[12, 16, 67, 43], 2반=[7, 17, 68, 48], 3반=[14, 15, 77, 54]로 주어질 때, 각 학급으로부터 능력치 16, 17, 15를 가진 학생을 각각 선택하면, 최댓값과 최솟값의 차이가 17-15=2로 최소가 된다.
대표로 선발된 모든 학생들 능력치의 최댓값과 최솟값 차이가 최소가 되는 경우의 값을 출력하는 프로그램을 작성하시오.
입력
입력의 첫 번째 줄에는 학급의 수를 나타내는 N과 각 학급의 학생의 수를 나타내는 M이 하나의 빈칸을 사이에 두고 주어진다. 단, 1 ≤ N, M ≤ 1,000이다. 두 번째 줄부터 N개의 줄에는 각 줄마다 한 학급 학생들의 능력치를 나타내는 M개의 양의 정수가 하나의 빈칸을 사이에 두고 주어진다. 능력치는 0이상 109이하이다.
출력
대표로 선발된 모든 학생들 능력치의 최댓값과 최솟값 차이가 최소가 되는 경우의 값을 하나의 정수로 출력한다.
풀이
대표로 선발된 모든 학생들 능력치의 최댓값과 최솟값 차이가 최소가 되는 경우의 값을 하나의 정수로 출력해야 한다.
먼저, 모든 학생을 하나의 list의 넣어준다. 이때 학생은 반과 능력치를 포함한 객체여야 한다.
그리고 능력치를 기준으로 오름차순 정렬한다.
그렇게 나열된 학생들에서 왼쪽에서 한 학생, 오른쪽에서 한 학생을 고르고, left, right를 포함해서 가운데 학생들이 각 반당 한 명 이상 존재한다면 그 경우 최댓값과 최솟값의 차이는 right.ablity - left.ablity가 된다.
단순히 모든 두 학생을 고르는 경우는 시간 초과로 문제를 풀 수 없다.
내가 푼 방식은 다음과 같다.
먼저, left를 0에 고정해 놓고, right를 최대한 왼쪽으로 보내준다.
여기서 학급 별 제외된 수를 표시하면서, 왼쪽으로 보내주면, 최대한이 어디까지인지 알 수 있다.
최대한은 각 반에서 한 명 이상씩 포함될 수 있다면 계속 왼쪽으로 right를 보내는 것을 말한다.
그렇게 되면 left는 0이고, right는 그 이상 왼쪽으로 갔을 때 각 반에서 한 명 이상씩 포함될 수 없는 위치에 있게 된다.
이때 right - left의 값을 answer에 넣어주고, 여기서 끝이 아닌
이번에는 left를 오른쪽으로 보내줘야 한다.
left를 오른쪽으로 한 칸 보내고, 제외된 학생을 체크해 준다.
이때 right는 가만히 있는게 최선이지만, 만약 각 반에서 제외된 수가 M명 이상이라면 right는 오른쪽으로 이동해야 한다. 그래야 각 반당 한 명 이상이라는 조건을 만족시켜줄 수 있기 때문이다.
그리고 right - left와 answer을 비교해 answer이 최소가 되는 값을 찾아나간다.
쉽게 말하자면, left 한 칸 오른쪽으로 움직였을 때 right가 최대한 왼쪽에 있으면서, 조건을 만족하는 위치로 움직이는 것을 반복한다는 것이다.
이 방식은 left가 움직일 때 right는 오른쪽으로만 움직일 수 있기 때문에 O(NM)으로 가능하다.
하지만 정렬이 있기 때문에 이 문제 자체의 시간 복잡도는 O(NMlogNM)이 된다.
소스 코드
import java.io.*;
import java.util.*;
class Student implements Comparable<Student> {
int cls, abl; //반, 능력치
Student(int cls, int abl) {
this.cls = cls;
this.abl = abl;
}
@Override
public int compareTo(Student o) {
if(this.abl < o.abl) {
return -1;
} else if(this.abl > o.abl) {
return 1;
}
return 0;
}
}
public class Main {
static int N, M;
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());
if(N == 1) {
System.out.println(0);
return;
}
M = Integer.parseInt(st.nextToken());
ArrayList<Student> list = new ArrayList<>();
for(int i=1; i<=N; i++) {
StringTokenizer st2 = new StringTokenizer(br.readLine());
for(int j=0; j<M; j++) {
list.add(new Student(i, Integer.parseInt(st2.nextToken())));
}
}
Collections.sort(list);
int[] exptClass = new int[N + 1]; //각 반 별 제외한 학생의 수
int left = 0;
int right = N * M - 1;
//left가 0일 때 right를 최대한 왼쪽으로 땡겨줄거임.
while(true) {
Student s = list.get(right); //제외했을 때 가능한지.
if(exptClass[s.cls] + 1 >= M) {
//현재 s를 제외했을 때 M보다 같거나 크다면 제외할 수 없음.
//right는 그대로
break;
}
//제외할 수 있음.
exptClass[s.cls] += 1;
right -= 1;
}
int answer = list.get(right).abl - list.get(left).abl;
boolean end = false;
//이제는 left를 오른쪽으로 전진시킨다.
while(true) {
left += 1; //left 커서를 오른쪽으로 전진. 그러면 바로 왼쪽은 제외된 것임.
Student s = list.get(left - 1); //제외된 학생
exptClass[s.cls] += 1;
while(true) {
if(exptClass[s.cls] < M) {
break;
}
//제외했을 때 M보다 크거나 같다면 결국 right를 조정해줘야 됨.
right += 1; //right 커서를 오른쪽으로 전진.
if(right == (N * M)) {
//right 커서가 범위를 넘어갔다면
end = true;
break;
}
Student rs = list.get(right); //포함될 학생.
exptClass[rs.cls] -= 1;
}
if(end) {
break;
}
answer = Math.min(answer, list.get(right).abl - list.get(left).abl);
}
System.out.println(answer);
}
}