2461 대표 선수

1. 풀이

 

 

1) 능력치 기준 오름차순 정렬

 

예제를 가지고 설명하겠다.

 

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

 

각 줄은 각 반 학생들의 능력치를 표시한다.

 

12 16 67 43 => 1반 학생
7 17 68 48 => 2반 학생
14 15 77 54 => 3반 학생

 

이 모든 능력치를 input 리스트에 Student 객체를 이용해서 넣을 것이다.

Student 클래스에는

'반' 을 의미하는 group 변수,

'능력치'를 의미하는 ability 변수가 있다.

 

12 16 67 43 는 1반 학생들의 능력치이기 때문에

Student 객체로 넣을 때

(1,12) (1,16) (1,67) (1,43) 이런식으로 넣어주면 된다.

 

그런 다음 input 리스트를 능력치 기준으로 오름차순 정렬한다.

 

(2,7) (1,12) (3,14) (3,15) (1,16) (2,17) (1,43) (2,48) (3,54) (1,67) (2,68) (3,77) 

 

이렇게 정렬된다.

즉 앞에 있는 값은 '반' 이고, 뒤에 있는 값은 '능력치'이다.

 

2) 두 포인터 

맨 처음 start = 0, end = 1 이다. => input 리스트의 인덱스를 나타낸다.

 

(1) 인덱스가 start = 0 일때의 input 값을 보자.

Student 객체 (2,7)가 있다.

즉, 2반 학생이며, 능력치가 7이다.

2번 학생이므로, 

visit[2] = 1이 된다.

 

(2) 인덱스가 end = 1 일때의 input 값을 보자.

Stduent 객체 (1,12) 가 있다.

visit[1] = 1이 된다.

 

=> 현재까지 visit[1] = 1, visit[2] = 1로,

1반 학생, 2반 학생이 1명씩 대표로 선발될 수 있지만, 아직 3반 학생은 참여하지 않았다.

그래서 3반 학생이 나올 때까지 end 를 증가시킨다.

 

(3) 인덱스 end = 2 일 때의 input 값을 보자.

Student 객체 (3,14) 가 있다.

visit[3] = 1이 된다.

 

그러면 이제 1,2,3 반 학생이 모두 1명씩 대표로 선발될 수 있다.

그래서 학생들 능력치의 최댓값과 최솟값의 차이를 구할 수 있다.

현재까지 선발된 학생들의 능력치가 7, 12, 14 이다.

그러면 14- 7 = 7 이 현재까지의 최댓값과 최솟값의 차이의 최소가 된다.

 

이때, 능력치 7은 input 리스트 0번째에 있는 능력치이고, start = 0 이다.

능력치 14는 input 리스트의 2번째에 있는 능력치이고, end = 2이다.

따라서 이처럼 두 포인터 start, end 를 이용해서 능력치 최댓값과 최솟값의 차이를 구할 수 있다.

 

이 과정이 끝나면 start를 1 증가시킨다. => start = 1

물론 이제 start = 0 인덱스의 학생은 대표선수로 선발되지 않을 것이므로

visit 배열의 값을 감소시킨다.

즉, 인덱스 0 일때 input 리스트에는 Student 객체 (2,7)가 있으므로,

2반 학생이다. 그래서 visit[2]를 1감소시키면 된다.

 

=> visit[1] = 1, visit[2] = 0, visit[3] = 1

 

이렇게 visit 배열에 1개라도 0이 생기면 그 반의 학생을 대표선수로 선발할 수 없으므로

2반 학생이 나올 때까지 end 를 증가시키면서 찾으면 된다.

 

 

3) 주의할 점

 

원래 처음에는 input 리스트가 아닌, 배열을 이용했다.

그런데 시간초과가 났다.

그 이유는 다음과 같다.

 

코드에 보면 input 리스트를 오름차순 정렬하는 과정이 있다.

(학생들 능력치 오름차순 정렬)

 

정렬할 때

배열은 최악의 경우 O(n^2) 의 시간이 걸릴 수 있고,

리스트는 최악의 경우 O(nlog(n)) 의 시간이 걸릴 수 있다.

 

그래서 배열이 아닌 리스트로 바꿔줬더니 시간초과가 나지 않았다.

 

시간초과 주의하자.

 

 

2. 최종 코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;
import java.util.stream.IntStream;


public class Main {
	
	static class Student {
		int group;
		int ability; 
		
		Student(int group, int ability) {
			this.group = group;
			this.ability = ability;
		}
	}
	
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " " );
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		ArrayList<Student> input = new ArrayList<>();
		
		
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int j=0;j<M;j++) {
			input.add(new Student(i+1, Integer.parseInt(st.nextToken())));
	     }
		}
		
		Collections.sort(input, new Comparator<Student> () {
			
			@Override
			public int compare(Student s1, Student s2) {
				return s1.ability - s2.ability;
			}
		});
	
		int visit [] = new int[N+1];
		visit[0] = 1;
		
		int min = Integer.MAX_VALUE;
		int start = 0;
		int end = 1;
		visit[input.get(start).group]++; 
		visit[input.get(end).group]++;
		
		
		while(end<N*M-1) {
			
			int zero = 0;
			
			if(IntStream.of(visit).anyMatch(x->x == zero)) {
			
				end++;
				
				if(end>=N*M) {
					break;
				}
				
				visit[input.get(end).group]++;
				 
			}else {
				
				min = Math.min(min, input.get(end).ability - input.get(start).ability);
				visit[input.get(start).group]--;
				start++;
				
				if(start>=N*M) {
					break;
				}
			}			
		}
		
		System.out.println(min);
    }
 }