[BOJ] 12764 - 싸지방에 간 준하 (Python, JavaScript)

 

 

아이디어

 

우선순위 큐를 이용하여 빈 자리를 확인하고, 빈 자리가 없는 경우 컴퓨터 수를 증가시킨다.

 

 

풀이 #1 (Python)

 

import sys
from heapq import heappush, heappop

input = sys.stdin.readline

def solution():
    N = int(input())
    times = [tuple(map(int, input().split())) for _ in range(N)]
    times.sort(key=lambda x: x[0])
    ends = []
    used = [0]
    available = [0]
    idx_dict = dict()
    cnt = 1
    for P, Q in times:
        while ends and ends[0] <= P:
            t = heappop(ends)
            heappush(available, idx_dict.get(t, 0))
        if available:
            idx = heappop(available)
            heappush(ends, Q)
            idx_dict[Q] = idx
            used[idx] += 1
        else:
            heappush(ends, Q)
            idx_dict[Q] = cnt
            used.append(1)
            cnt += 1
    print(cnt)
    print(' '.join(map(str, used)))

solution()

 

 

딕셔너리를 사용하지 않고 인덱스를 종료 시각과 함께 넣을 수도 있지만 힙 정렬 때문에 더 느린 듯하다.

# 메모리를 더 적게 사용하지만 더 느린 코드
...
for P, Q in times:
    while ends and ends[0][0] <= P:
        _, idx = heappop(ends)
        heappush(available, idx)
    if available:
        idx = heappop(available)
        heappush(ends, (Q, idx))
        used[idx] += 1
    else:
        heappush(ends, (Q, cnt))
        used.append(1)
        cnt += 1
...

 

 

 

풀이 #2 (JavaScript)

 

힙을 직접 구현하고, 파이썬의 딕셔너리를 대신하여 자바스크립트에서는 맵을 사용한다.

 

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

class Heap {
    constructor(e) {
        this.heap = [-1, ...e || []];
    }
    
    push(e) {
        let heap = this.heap;
        heap.push(e);
        let idx = heap.length-1;
        while (parseInt(idx/2) > 0) {
            const p = parseInt(idx/2);
            if (heap[idx] < heap[p]) [heap[idx], heap[p]] = [heap[p], heap[idx]];
            else break;
            idx = p;
        }
    }
    
    pop() {
        let heap = this.heap;
        if (heap.length > 1) {
            [heap[1], heap[heap.length-1]] = [heap[heap.length-1], heap[1]];
            const e = heap.pop();
            let idx = 1;
            while (idx*2 < heap.length) {
                let child = idx;
                let left = idx*2;
                let right = idx*2+1;
                if (heap[left] < heap[idx]) child = left;
                if (right < heap.length && heap[right] < heap[child]) child = right;
                if (child === idx) break;
                [heap[idx], heap[child]] = [heap[child], heap[idx]];
                idx = child;
            }
            return e;
        }
        return -1;
    }
    
    peek() {
        let heap = this.heap;
        if (heap.length > 1) return heap[1];
        return -1;
    }
    
    length() {
        return this.heap.length-1;
    }
}

function solution() {
    const N = Number(input[0]);
    let times = [];
    for (let i=1; i<=N; i++) times.push(input[i].split(' ').map(Number));
    times.sort((a, b) => a[0]-b[0]);
    let ends = new Heap();
    let used = [0];
    let available = new Heap([0]);
    let idxMap = new Map();
    let cnt = 1;
    for (const [P, Q] of times) {
        while (ends.length() && ends.peek() <= P) {
            const t = ends.pop();
            available.push(idxMap.get(t));
        }
        if (available.length()) {
            const idx = available.pop();
            ends.push(Q);
            idxMap.set(Q, idx);
            used[idx] += 1;
        }
        else {
            ends.push(Q);
            idxMap.set(Q, cnt);
            used.push(1);
            cnt += 1;
        }
    }
    console.log(cnt);
    console.log(used.join(' '));
}

solution();