[백준] 2461 대표선수 #JAVA #투포인터

[백준] 2461 대표선수 #JAVA #투포인터

 

---

코드

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

	static int N,M;
	static int count[];
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st;
		
		st= new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());//학급
		M = Integer.parseInt(st.nextToken());//학급별 학생 수
		count = new int[N];
		
		List<int[]> student = new ArrayList<>();  
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			
			for (int j = 0; j < M; j++) {
				student.add(new int[] {i,Integer.parseInt(st.nextToken())}); //학급,능력치
			}
		}

		student.sort((a,b)-> a[1]-b[1]); // 능력치 순서로 정렬
		
		int lp = 0;
		int rp = 0;

		int diff= Integer.MAX_VALUE;
		
		while (lp < N*M-1 && rp < N*M-1) {

			//모든 학급이 포함되도록 rp값 이동
			while (rp < N*M-1) {
				
				count[student.get(rp++)[0]]++;
				
				if(haveAllClass()) break;
			}
			
			//모든 학급이 포함되도록 lp값 이동
			while (count[student.get(lp)[0]]>1) {
				count[student.get(lp++)[0]]--;
			}

			//모든 학급 포함시 값 갱신
			if(haveAllClass()) {
				int min = Integer.MAX_VALUE;
				int max = Integer.MIN_VALUE;
				
				for (int i = lp; i < rp; i++) {
					min = Math.min(min, student.get(i)[1]);
					max = Math.max(max, student.get(i)[1]);
				}
				diff = Math.min(diff, max-min);
			}
			
			//lp 오른쪽으로 한칸 이동
			count[student.get(lp++)[0]]--;
			
		}
		System.out.println(diff);
		
	}

	private static boolean haveAllClass() { //모든 학급이 포함되었는지 확인하는 함수
		for (int cnt : count) {
			if(cnt == 0) return false;
		}
		
		return true;
	}
}

 

 

풀이

---

1. 능력치 순서대로 학생을 정렬한다. 이 때 학급의 정보를 확인 할 수 있어야 한다.
2. 투 포인터를 활용하여 모든 학급의 학생이 포함되는 연속된 범위를 찾아낸다. 
3. 해당 범위에서 최댓값-최솟값 이 최소가 되는 값을 갱신한다.

 

주의 사항

---

• lp, rp 범위 주의

 

 

 

 

---

잘못된 코드나 내용이 있다면 댓글을 남겨주세요. 즉시 수정하도록 하겠습니다! :)