[백준] 2461번 대표 선수 자바

문제

 

2461번: 대표 선수

 

 

 

문제 풀이

 

학급 대표선수 간 최대 최소 차가 최소가 되기위해서는 최대한 비슷한 값끼리 묶여있어야 하므로 모든 학생들을 학급 표시만 해둔 채로 정렬시켰다. 그리고 두 개의 인덱스 변수로 첫번째 선수를 마킹해두고, 뒤로 가면서 모든 학급이 다 찰때까지 두번 째 인덱스를 증가시켜 나갔다. 그 때의 최솟값을 갱신하면서 첫번째 인덱스를 증가하면서 나갔는데 시간초과가 떴다.

 

이를 개선하기 위해서 한 학급에서 나온 대표선수를 표시해두기 위해 boolean배열이 아닌 int배열을 사용했다.

int배열에 모든 학급의 대표선수가 뽑힐 때까지 지나온 학급의 개수를 카운트해서 넣어주었고, 모든 학급을 담았을 때는 차이값 갱신하고, 첫번째 인덱스의 int배열의 값을 하나 뺀다. 뺐을 때 0이되었으면 다시 한 학급이 부족하므로 다시 모든 학급이 찰 때까지 두번째 인덱스를 증가해나간다. 만약, 0이 안되었을 경우엔 같은 학급이 반복되어 나올 경우로 바로 값을 갱신할 수 있다.

이렇게 만약 미리 모든 학급이 나온 경우에 두번째 인덱스가 모든 학급을 채우지 못해 전체 학생의 배열 끝까지 가고 반복문을 탈출하게 된다.

 

+다른풀이)

1. 학급 별로 능력치 정렬 후

2. 각 학급의 제일 첫번째를 각각 가리키는 포인터 설정
3. 학급 별 정렬의 첫번째 값(포인터 값들) 중 제일 최솟값과 최댓값 추출

4. 차이값 갱신

5. 최솟값이 나온 학급을 다음 학생으로 포인터 옮김 

6. 그리고 그 포인터 값들 중 최소 최대를 다시 구해 차이값 갱신

7. 한 학급이 끝날때까지 계속 반복

 

소스 코드

 

public class b_2461 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] str = br.readLine().split(" ");
		
		int N = Integer.parseInt(str[0]);	//학급수
		int M = Integer.parseInt(str[1]);	//학급인원
		Student[] total = new Student[N * M];
		int idx = 0, answer = Integer.MAX_VALUE;
		
		//input
		for(int i = 0; i < N; i++) {
			str = br.readLine().split(" ");
			for(int j = 0; j < M; j++)
				total[idx++] = new Student(Integer.parseInt(str[j]), i);
		}
		Arrays.sort(total);

		int[] count = new int[N];	//학급별 개수 카운트
		idx = 0;
		int idx2 = 0, cnt = 0;
		while(idx2 < N * M) {
			if(count[total[idx2].cls] == 0)
				cnt++;
			count[total[idx2].cls]++;
			idx2++;
			
			while(cnt == N) {
				answer = Math.min(answer, total[idx2-1].ability - total[idx].ability);
				count[total[idx].cls]--;
				if(count[total[idx].cls] == 0)
					cnt--;
				idx++;
			}
		}
		
		System.out.println(answer);
	}

}

class Student implements Comparable<Student>{
	int ability, cls;
	
	public Student(int ability, int cls) {
		this.ability = ability;
		this.cls = cls;
	}

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