bj2461(대표 선수)-N 포인터, 우선순위 큐

https://www.acmicpc.net/problem/2461

 

이 문제는 투 포인터보다는 구현 문제같다.

이 문제의 킥은 최소와 최대값만 알면 된다는 것이다.

 

우선, 모든 반을 정렬 시킨다.

0에 N개의 포인터를 고정하고, while문을 실행한다.

최대와 최소의 합이 최소가 되기 위해서는 최소값을 증가시켜 주어야 한다.

때문에, 정렬되어있는 배열에서 최솟값을 한 칸 증가시킨다.

이게 다다.

 

투포인터는 정렬되어있는 어떤 자료들에서

Left를 옮기면 커지고

Right를 옮기면 작아진다

는 개념이다.

즉, 최소를 옮기면, (최댓값 - 최솟값에서 최솟값이 증가하니) 값이 작아진다.

는 개념을 이용해서 투 포인터라고 문제 유형에 있던것같은데,

내가 봤을 때는 그냥 구현같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N, M;
    static int[][] nums;
    static StringTokenizer stringTokenizer;
    static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws IOException {
        initialize();
        System.out.println(solve());
    }

    private static int solve() {
        int answer = Integer.MAX_VALUE;
        int max = 0;
        PriorityQueue<int[]> pointer = new PriorityQueue<>((o1, o2) -> o1[0] - o2[0]);
        for(int y = 0; y < N; y++){
            pointer.add(new int[]{nums[y][0], y, 0});
            max = Math.max(max, nums[y][0]);
        }
        while(true){
            int[] temp = pointer.poll();
            int min = temp[0];
            int ty = temp[1];
            int tx = temp[2];
            answer = Math.min(max - min, answer);

            if(tx+1 >= M)break;

            max = Math.max(nums[ty][tx+1], max);
            pointer.add(new int[]{nums[ty][tx+1], ty, tx+1});
        }
        return answer;
    }

    private static void initialize() throws IOException {
        stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        N = Integer.parseInt(stringTokenizer.nextToken());
        M = Integer.parseInt(stringTokenizer.nextToken());
        nums = new int[N][M];
        for(int y = 0; y < N; y++){
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            for(int x = 0; x < M; x++){
                nums[y][x] = Integer.parseInt(stringTokenizer.nextToken());
            }
            Arrays.sort(nums[y]);
        }
    }
}