20개 중에 하나만 맞고 장렬히 전사..

function solution(jobs) {
    var answer = 0;
    
    let sum = 0;
    let waitingTime = 0
    let indexSet = new Set()
    while (indexSet.size < jobs.length){
        let minElement = [0, 1000]
        let minIndex
        for (i = 0; i<jobs.length; i++){
            if(indexSet.has(i)) continue
            if(jobs[i][0] > sum) break
            if(jobs[i][1] < minElement[1]) {
                minElement = jobs[i]
                minIndex = i
            }
        }
        sum += minElement[1]
        waitingTime += sum-minElement[0]
        indexSet.add(minIndex)
    } 
    answer = Math.floor(waitingTime/jobs.length)
    
    return answer;
}

현재 시간까지 들어온 요청 중에 가장 낮은 녀석들부터 실행해야 한다는 건 알겠는데,
자료구조에 대한 이해가 부족해서 못푸는 중...

시간 초과난 케이스가 별로 없으므로 일단 예외처리부터 할 예정.

우선, 시간 내에 들어온 요청이 없을 경우, 시간을 더 기다린다

function solution(jobs) {
    var answer = 0;
    
    let sum = 0;
    let waitingTime = 0
    let indexSet = new Set()
    while (indexSet.size < jobs.length){
        let minElement = [0, 1001]
        let minIndex = -1
        for (i = 0; i<jobs.length; i++){
            if(indexSet.has(i)) continue
            if(jobs[i][0] > sum) break
            if(jobs[i][1] < minElement[1]) {
                minElement = jobs[i]
                minIndex = i
            }
        }
        if(minIndex < 0) {
            sum += 1
            continue
        }
        sum += minElement[1]
        waitingTime += sum-minElement[0]
        indexSet.add(minIndex)
    } 
    answer = Math.floor(waitingTime/jobs.length)
    
    return answer;
}

3개 통과로 갯수가 늘고 시간 초과도 사라졌다.

혹시나 테스트 케이스와는 다르게 jobs가 정렬이 안되어 있는건 아닌가 해서 sort를 실행하였다.

function solution(jobs) {
    var answer = 0;
    
    let sum = 0;
    let waitingTime = 0
    let indexSet = new Set()
    jobs.sort((a,b) => {
        return a[0]-b[0]
    })
    while (indexSet.size < jobs.length){
        let minElement = [0, 1001]
        let minIndex = -1
        for (i = 0; i<jobs.length; i++){
            if(indexSet.has(i)) continue
            if(jobs[i][0] > sum) break
            if(jobs[i][1] < minElement[1]) {
                minElement = jobs[i]
                minIndex = i
            }
        }
        if(minIndex < 0) {
            sum += 1
            continue
        }
        sum += minElement[1]
        waitingTime += sum-minElement[0]
        indexSet.add(minIndex)
    } 
    answer = Math.floor(waitingTime/jobs.length)
    
    return answer;
}

채점을 시작합니다.
정확성  테스트
Test 1 〉	통과 (10.66ms, 36.7MB)
Test 2 〉	통과 (321.45ms, 36.6MB)
Test 3 〉	통과 (51.33ms, 36.5MB)
Test 4 〉	통과 (30.87ms, 36.6MB)
Test 5 〉	통과 (6.40ms, 36.5MB)
Test 6 〉	통과 (0.27ms, 33.4MB)
Test 7 〉	통과 (4.99ms, 36.6MB)
Test 8 〉	통과 (4.63ms, 36.5MB)
Test 9 〉	통과 (0.94ms, 33.5MB)
Test 10 〉	통과 (6.70ms, 36.6MB)
Test 11 〉	통과 (0.22ms, 33.4MB)
Test 12 〉	통과 (0.24ms, 33.4MB)
Test 13 〉	통과 (0.21ms, 33.4MB)
Test 14 〉	통과 (0.19ms, 33.5MB)
Test 15 〉	통과 (0.19ms, 33.4MB)
Test 16 〉	통과 (0.12ms, 33.4MB)
Test 17 〉	통과 (0.09ms, 33.5MB)
Test 18 〉	통과 (0.10ms, 33.5MB)
Test 19 〉	통과 (0.10ms, 33.4MB)
Test 20 〉	통과 (0.11ms, 33.4MB)
Submission result
정확성: 100.0
Total score: 100.0 / 100.0

결론은 통과...

해설

해당 문제는 '우선순위 큐'를 이용한 문제이다.

'큐'자료구조는 가장 앞의 배열을 제거한다.
'우선순위 큐'는 쉽게 말해 우선순위 순으로 '정렬'한 후, 가장 앞의 배열을 제거하면 된다.

우선순위 큐는 다른 언어에서는 '힙' 자료구조를 이용해 구현된다. 힙 자료구조는 '완전이진트리'형태이며, 새로운 요소가 추가되면 부모 요소와 비교하여 자리를 바꾼다. 최악의 경우 새로 추가된 요소가 루트 노드까지 거슬러 올라가 비교하게 되며, 이 때 트리의 높이가 log n이므로 시간 복잡도는 O(log n)이 되며, 본 문제를 힙으로 구현할 경우 시간 복잡도는 O(n log n)이 된다.

자바스크립트에서는 heap을 구현한 메서드가 없다.
따라서 본 문제는 우선순위 큐를 통해 O(n^2)으로 구현하면 된다.

위 문제의 해답은 아래와 같다.

1. 요청 배열을 요청이 들어온 시간 순으로 정렬한다.
2. '현재 시간'을 기준으로 지금까지 들어온 요청을 slice하여 '큐'라는 배열에 넣는다.
3. '큐'에 새로운 요청이 들어올 때마다 처리 시간을 기준으로 정렬한다.
4. '큐'에 가장 앞에 있는 녀석부터 Array.shift로 처리한다.
5. 만일 '큐'에 남아있는 요소가 없다면 현재 시간에 +1.
6. 만일 요청 배열에 남아있는 요소가 없다면 종료한다.

핵심은 '현재 시간'이 변할 때마다 큐에 새로운 요청이 추가될 수 있으며,
큐에 새로운 요청이 추가될 때마다 정렬을 수행한다는 점이다.

아래는 chatGPT가 풀이한 내용이다.

우선순위 큐

function solution(jobs) {
    const n = jobs.length;
    jobs.sort((a,b) => a[0]-b[0]); // 시작 시간을 기준으로 정렬

    let sum = 0, waitingTime = 0, index = 0;
    const pq = []; // 우선순위 큐 생성

    while (index < n || pq.length > 0) { // 처리할 작업이 남아있을 때까지 반복
        if (pq.length === 0) { // 처리할 작업이 없으면 가장 먼저 들어온 작업을 대기열에서 꺼내서 처리
            sum = jobs[index][0];
        } else { // 우선순위 큐에 작업이 있으면 종료 시간을 기준으로 가장 짧은 작업부터 처리
            const job = pq.shift();
            waitingTime += sum - job[0] + job[1];
            sum += job[1];
        }

        while (index < n && jobs[index][0] <= sum) { // 새로운 작업들을 우선순위 큐에 추가
            pq.push(jobs[index]);
            index++;
        }

        pq.sort((a,b) => a[1]-b[1]); // 종료 시간을 기준으로 정렬
    }

    return Math.floor(waitingTime / n);
}