자바(백준) 2461 대표 선수

오답 노트 & 새로 알게 된 점

해당 문제는 처음에 읽고 어떻게 풀어야할지 감이 안왔다.

 

1. 처음에는 완탐을 생각하면서 일일이 구할 생각을 했지만, 당연히 TLE다.

2. class마다 포인터를 두어 하나하나 탐색하려고 했다. 하지만 이 방법도

1번 방법과 다른 점이 없고, class의 개수는 항상 달라지는데 이걸 구분할 방법도 생각나지 않았다.

 

결국 풀이를 보고 문제를 해결했다.

문제 해결을 하기 위해 문제를 바꾸는 것이 중요한 부분이다.

 

모든 학생들을 능력치 오름차순으로 일렬로 정렬을 한다. 

여기서 해당 학생은 어느 class에 속해있는지 알아야한다.

 

일렬로 정렬하고 두 포인터를 이용하여 

N개의 class가 모두 포함되면 그 때 능력 차이를 구하면 된다.

 

---

코드

package TwoPointers;
 
import java.io.*;
import java.util.*;
 
public class BOJ2461 {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static int N, M;
    static ArrayList<Student> al = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        input();
        pro();
    }
 
    static void pro() {
        Collections.sort(al, (o1, o2)->{
            return o1.abil - o2.abil;
        });
 
        int s = 0, e = 0;
        int count[] = new int[N];
        int min = al.get(al.size() - 1).abil - al.get(0).abil;
        count[al.get(0).cls] += 1;
        int cnt = 1; //각 학급이 모두 들어가있는지 확인
 
        while (true) {
            //각 학급의 대표자들이 1명씩 뽑힌 상황
            if (cnt == N) {
                min = Math.min(min, al.get(e).abil - al.get(s).abil);
                count[al.get(s).cls] -= 1;
                if(count[al.get(s).cls] == 0) cnt--;
                s++;
            } else if (cnt < N) {
                e++;
                if(e == al.size()) break;
 
                if(count[al.get(e).cls] == 0){
                    cnt++;
                }
                count[al.get(e).cls] += 1;
            }
        }
        System.out.println(min);
    }
 
    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = atoi(st.nextToken());
        M = atoi(st.nextToken());
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                int abli = atoi(st.nextToken());
                al.add(new Student(abli, i));
            }
        }
 
    }
    static class Student{
        int abil, cls;
 
        public Student(int abil, int cls) {
            this.abil = abil;
            this.cls = cls;
        }
    }
}