2461 대표 선수 ( 자바스크립트 )

문제

KOI 중학교에는 N개의 학급이 있으며, 각 학급의 학생 수는 모두 M명으로 구성된다. 이 중학교에서는 체육대회에 새로운 종목의 경기를 추가하였다. 이 경기에 대해 모든 학생들은 저마다의 능력을 나타내는 능력치를 가지고 있으며, 이 능력치는 모든 학생이 서로 다르다.

이 경기는 한반에서 한 명의 대표선수를 선발하여 치른다. 경기의 형평성을 위하여, 각각의 반에서 대표로 선발된 모든 학생들의 능력치 중 최댓값과 최솟값의 차이가 최소가 되도록 선수를 선발하려고 한다. 예를 들어, N=3, M=4인 경우 학생들의 능력치가 1반=[12, 16, 67, 43],  2반=[7, 17, 68, 48], 3반=[14, 15, 77, 54]로 주어질 때, 각 학급으로부터 능력치 16, 17, 15를 가진 학생을 각각 선택하면, 최댓값과 최솟값의 차이가 17-15=2로 최소가 된다. 

대표로 선발된 모든 학생들 능력치의 최댓값과 최솟값 차이가 최소가 되는 경우의 값을 출력하는 프로그램을 작성하시오.

입력

입력의 첫 번째 줄에는 학급의 수를 나타내는 N과 각 학급의 학생의 수를 나타내는 M이 하나의 빈칸을 사이에 두고 주어진다. 단, 1 ≤ N, M ≤ 1,000이다. 두 번째 줄부터 N개의 줄에는 각 줄마다 한 학급 학생들의 능력치를 나타내는 M개의 양의 정수가 하나의 빈칸을 사이에 두고 주어진다. 능력치는 0이상 109이하이다.

출력

대표로 선발된 모든 학생들 능력치의 최댓값과 최솟값 차이가 최소가 되는 경우의 값을 하나의 정수로 출력한다.

====

문제 풀이

우선 입력값으로 들어오는 각 학급의 학생들을 오름차순으로 정렬한 뒤 col이 0인 애들(각 학급에서 제일 작은 애들)을 최소 힙큐에 다 넣어준다. 이때 min 과 max를 구하여 초기 diff를 생성한다.

const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

const [n, m] = input[0].split(' ').map(Number);
const arr = input.slice(1).map((s) =>
    s
        .split(' ')
        .map(Number)
        .sort((a, b) => a - b)
);

const q = new Heapq();

let min = Infinity;
let max = 0;

for (let i = 0; i < n; i++) {
    q.push([arr[i][0], i, 0]);
    min = Math.min(min, arr[i][0]);
    max = Math.max(max, arr[i][0]);
}

let diff = max - min;

 

그 뒤 힙큐에서 하나를 꺼내면 이 요소는 지금까지의 대표 선수들 중 가장 작은 값이 빠져나가게 되고, 그 빠진 대표선수 자리에는 동일 학급의 다음 인덱스(오름차순 정렬 되어 있으므로 그 다음으로 큰 수)를 힙큐에 넣어준다. 

이때 힙큐의 루트는 지금의 대표 선수들 중 가장 작은 값이 된다. 가장 큰수는 기존 max와 직전에 넣은 대표 선수를 비교하여 더 큰값으로 입혀준다. 

이제 diff와 (max - 힙큐 루트) 를 비교해주어 최대-최소 중 더 작은 값을 기록해준다. 

이 과정의 종료 시점은 힙큐에서 하나를 꺼낸 뒤 그 해당 학급의 다음 인덱스가 더이상 없을 경우이다. (다음 인덱스가 없다는 것은 더이상 대표 선수단을 꾸릴 수 없다는 뜻이므로)

while (true) {
    const [_, row, col] = q.pop();
    if (col === m - 1) break;
    const next = arr[row][col + 1];
    q.push([next, row, col + 1]);

    min = q.returnMin();	// 힙큐의 루트 요소
    max = Math.max(max, next);

    diff = Math.min(diff, max - min);
}

console.log(diff);

 

정답 코드

class Heapq {
    #hq;
    constructor() {
        this.#hq = [undefined];
    }
    isEmpty() {
        return this.#hq.length === 1;
    }
    size() {
        return this.#hq.length;
    }
    swap(src, des) {
        [this.#hq[src], this.#hq[des]] = [this.#hq[des], this.#hq[src]];
    }
    isSmall(src, target) {
        if (this.#hq[src][0] < this.#hq[target][0]) {
            return true;
        }
        return false;
    }
    print() {
        console.log(this.#hq);
    }
    push(arr) {
        this.#hq.push(arr);
        let cur = this.size() - 1;
        while (cur > 1) {
            const parent = Math.floor(cur / 2);
            if (this.isSmall(cur, parent)) {
                this.swap(cur, parent);
                cur = parent;
            } else {
                break;
            }
        }
    }
    pop() {
        if (this.isEmpty()) return undefined;
        const root = this.#hq[1];
        const last = this.#hq.pop();
        if (this.isEmpty()) return last;
        this.#hq[1] = last;
        let cur = 1;

        while (cur * 2 < this.size()) {
            let smallest = cur * 2;
            if (smallest + 1 < this.size()) {
                const right = smallest + 1;
                if (this.isSmall(right, smallest)) {
                    smallest = right;
                }
            }
            if (this.isSmall(smallest, cur)) {
                this.swap(smallest, cur);
                cur = smallest;
            } else {
                break;
            }
        }

        return root;
    }
    returnMin() {
        return this.#hq[1][0];
    }
}

const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

const [n, m] = input[0].split(' ').map(Number);
const arr = input.slice(1).map((s) =>
    s
        .split(' ')
        .map(Number)
        .sort((a, b) => a - b)
);

const q = new Heapq();

let min = Infinity;
let max = 0;

for (let i = 0; i < n; i++) {
    q.push([arr[i][0], i, 0]);
    min = Math.min(min, arr[i][0]);
    max = Math.max(max, arr[i][0]);
}

let diff = max - min;

while (true) {
    const [_, row, col] = q.pop();
    if (col === m - 1) break;
    const next = arr[row][col + 1];
    q.push([next, row, col + 1]);

    min = q.returnMin();
    max = Math.max(max, next);

    diff = Math.min(diff, max - min);
}

console.log(diff);

 

 

 

while (true) {
const [_, row, col] = q.pop ();
if (col === m -1) 파손;
const next = arr [row] [col + 1];
Q.push ([다음, 행, col + 1]);

최소 = Q.returnmin (); // 힙큐의 루트 힙큐의
max = math.max (max, next);

diff = math.min (diff, max -min);
}

Console.log (diff);