[JS/Programmers] 17678. [1차] 셔틀버스

💬 문제

문제 난이도: Programmers Lv.3

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/17678

❗️접근방법

구현... (여러가지의 경우의 수를 자알 떠올려야)

👆 코드

class MinHeap{
    constructor(){
        this.heap = [null];
    }
    size(){
        return this.heap.length -1;
    }
    getMin(){
        return this.heap[1] ? this.heap[1] : null;
    }
    swap(a, b){
        [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
    }
    heappush(value){
        this.heap.push(value);
        let curIdx = this.heap.length-1;
        let parIdx = (curIdx / 2) >> 0;
        
        while(curIdx > 1 && this.heap[parIdx] > this.heap[curIdx]){
            this.swap(parIdx, curIdx);
            curIdx = parIdx;
            parIdx = (curIdx / 2) >> 0;
        }
    }
    heappop(){
        const min = this.heap[1];
        if(this.heap.length <= 2) this.heap = [null];
        else this.heap[1] = this.heap.pop(); // 맨 뒤에 있는 노드를 루트 노드로 올림
        
        let curIdx = 1;
        let leftIdx = curIdx * 2;
        let rightIdx = curIdx * 2 + 1;
        
        if(!this.heap[leftIdx]) return min; // 왼쪽 자식 노드가 없다. -> cur노드가 리프노드
        if(!this.heap[rightIdx]){ // 왼쪽 자식은 있지만 오른쪽 자식이 없다.
            if(this.heap[leftIdx] < this.heap[curIdx]) this.swap(leftIdx, curIdx);
            return min;
        }
        // 왼쪽 오른쪽 자식 모두 있다.
        while(this.heap[leftIdx] < this.heap[curIdx] || this.heap[rightIdx] < this.heap[curIdx]){
            const minIdx = this.heap[leftIdx] > this.heap[rightIdx] ? rightIdx : leftIdx;
            this.swap(minIdx, curIdx);
            curIdx = minIdx;
            leftIdx = curIdx * 2;
            rightIdx = curIdx * 2 + 1;
        }
        return min;
    }
}

function makeAnswerForm(num){
    let hour = (num / 60)>>0;
    let min = num % 60;
    if (hour<10) hour = "0"+hour;
    if (min<10) min = "0"+min;
    return hour+":"+min;
}

function solution(n, t, m, timetable) {
  
    if(timetable.length < m){ // --- 1️⃣
        const total = 540 + (n-1)*(t);
        return makeAnswerForm(total)
    }
    const minHeap = new MinHeap();

    for (const elem of timetable){ // --- 2️⃣
        let [hour, min] = elem.split(':');
        hour = parseInt(hour) * 60;
        min = parseInt(min);
        minHeap.heappush(hour+min);
    }
    
    let now = 540;
    for (let i = 0; i < n-1; i+=1){ // --- 3️⃣
        for (let j = 0;  j < m; j+=1){
            const crew = minHeap.heappop();
            if (now < crew) {
                minHeap.heappush(crew);
                break;
            }
        }

        now += t;
    }
    
    const lastShuttle = [];
    for (let i = 0; i < m; i+=1){ // --- 4️⃣
        if (minHeap.size() <= 0) break;
        const crew = minHeap.heappop();
        if (crew <= now) lastShuttle.push(crew); 
        else break;
    }
    if (lastShuttle.length === m){ // --- 5️⃣
        return makeAnswerForm(lastShuttle[m-1]-1);
    }else{
        return makeAnswerForm(now); // --- 6️⃣
    }
}

구현 방법
1️⃣ 콘을 포함한 이미 줄을 선 크루들이 한 반에 셔틀을 타도 되는 경우
-> 제일 마지막 셔틀 시간을 리턴
2️⃣ HH:MM 포맷의 timetable 원소를 숫자 형태로 바꿔서 minHeap에 추가
3️⃣ 첫 번째 셔틀부터 n-1번째의 셔틀까지 태울 수 있는 크루들 태우기(=힙에서 팝하기)
4️⃣ 마지막 셔틀에 태움.
-> 이때, minHeap에 null이 아닌 원소가 들어있는지 확인하자.(== size > 0)
-> 그렇지 않으면 null과 now를 비교하게 되는 불상사가 발생한다.
5️⃣ 마지막 셔틀에 m명이 모두 탔다면 (마지막에 셔틀을 탄 사람 - 1)에 콘이 줄을 서면 된다.
-> 마지막에 셔틀을 탄 사람보다 적어도 1분은 일찍 와야 탈 수 있으니까
6️⃣ 마지막 셔틀에 m명 미만이 탔다면 마지막 셔틀이 떠나는 시간인 now에 콘이 줄을 서면 된다.

console.log(null <= 540); // true

null >= 0; //true
null <= 0; //true
null == 0; //false
null > 0;  //false
null < 0;  //false

null > 0 이 false니까 null <= 0 은 true
null < 0 이 flase니까 null >= 0 은 true
=> null과 숫자를 비교하는 상황을 만들지 말자..