[프로그래머스/level2/JS] 과제 진행하기

문제 링크

[프로그래머스/Level2/JS] 과제 진행하기

문제 풀이

[과목이름, 과제 시작시간, 과제 소요시간]이 배열로 주어지고 과제를 수행하는 알고리즘이 주어질 때 과제를 해결하는 순서를 배열에 담아서 반환해야하는 문제이다. 이 문제를 보고 CPU 스케쥴링과 비슷하다는 생각이 들었던 것 같다.

 

우선 과제 수행 알고리즘을 먼저 살펴보자.

1. 과제는 시작하기로 한 시간이 되면 시작한다.

2. 새로운 과제를 시작할 시간이 되었을 때, 기존에 진행 중이던 과제가 있을 경우 진행 중이던 과제를 멈추고 새로운 과제를 시작한다.

3. 진행중이던 과제가 끝났을 때, 멈춘 과제가 있다면, 멈춘 과제를 이어서 진행한다.

    - 만약, 과제를 끝낸 시각에 새로 시작해야하는 과제와 잠시 멈춰둔 과제가 있을 경우 새로 시작해야하는 과제부터 시작한다.

4. 멈춰둔 과제가 여러 개일 경우 가장 최근에 멈춘 과제부터 시작한다. => stack을 떠올릴 수 있을 것 같다.

 

알고리즘만 봐도 극강의 J인 것 같다.

 

위 4가지 알고리즘만 구현해주면 쉽게 문제를 해결할 수 있을까? 시간 초과가 나는 함정이 있지 않을까?

시간에 관여하는 조건들을 확인해보자.

 

1. 3 <= plans <= 1000

=> 수행할 과제의 목록이 10^3

2. plans의 두번째 원소는 과제의 시작 시간으로 00:00 ~ 23:59의 시간 값만 가진다.

=> 분으로 변환 시 60 * 24 = 1440(10^3)의 가지의 시작 시간이 존재한다.

 

그렇다면 1분 간격으로 모든 plans의 시간 및 상태를 조사하더라도 10^3 * 10^3 = 10^6을 가진다. 직관적으로 구현하더라도 시간초과는 나지 않을 것으로 판단할 수 있다.

 

최악의 경우에는 1분 간격으로 과제를 배치하는 것이겠지만 구현 시에는 조금 더 효율적으로 구현할 수 있을 것 같다.

우선 주어진 과제들을 시작 순으로 배치한 후에 현재 과제 끝나는 시간과 다음 과제 시작 시간을 비교하면 어떨까?

 

즉 [현재 과제 시작 시간 + 현재 과제 소요시간], [다음 과제 시작 시간]을 비교하는 것이다.

비교 결과에 따라 취해야할 행동을 구분하자면 다음과 같다.

 

1. 현재 과제 시작 시간 + 현재 과제 소요시간 > 다음 과제 시작 시간

현재 과제가 끝나기 전에 다음 과제를 수행해야 하는 경우이다. 그렇다면 현재 수행하던 과제는 stack에 넣어놓도록 하자. 이때 넣어둘 때 더이상 시작 시간은 의미가 없으므로 과제 이름과 남은 과제 시간을 담은 배열로 넣어놓자.

 

2. 현재 과제 시작 시간 + 현재 과제 소요 시간 === 다음 과제 시작 시간

현재 과제를 끝낸 시간이 다음 과제 시작 시간과 같은 경우이다. 이럴때는 수행 알고리즘 3번에 의하여 새로 시작하는 과제부터 시작한다.

 

3. 현재 과제 시작 시간 + 현재 과제 소요 시간 < 다음 과제 시작 시간

현재 과제를 다음 과제 시작 전에 끝낸 경우이다. 이럴때도 수행 알고리즘 3번, 4번에 의하여 가장 최근에 멈춘 과제부터 시작한다.

 

그리고 plans에 있는 과제가 더이상 없다면 stack에 있는 과제들을 pop하면서 마저 끝내준다.

 

이제 위 행동을 바탕으로 코드를 짜면 쉽게 정답을 맞출 수 있다.

코드

function solution(plans) {
    const answer = [];
    const stack =[];
    
    const getMinutes = (time) => {
        const [ hours, minutes ] = time.split(':');
        
        return hours * 60 + minutes * 1;
    }
    
    const minutesPlans = plans.map(([subject, time, spendTime]) => {
        return [subject, getMinutes(time), spendTime * 1];
    })
    
    minutesPlans.sort((a, b) => a[1] - b[1]);
    
    while(minutesPlans.length) {
        const [ subject, currentTime, spendTime ] = minutesPlans.shift();
        
        if(minutesPlans.length) {
            const [ _, nextTime ] = minutesPlans[0];
            
            if(currentTime + spendTime > nextTime) {
            	// 과제를 다음 과제 전에 끝내지 못한 경우
                stack.push([ subject, currentTime + spendTime - nextTime]);
            } else {
            	// 과제를 시간 내에 끝낸 경우
                answer.push(subject);
                
                if(stack.length && currentTime + spendTime !== nextTime) {
                	// 과제가 다음 과제 시작 시간 전에 일찍 끝난 경우에만 plans 앞으로 넣어준다.
                    const [ qSubject, qTime ] = stack.pop();
                    
                    minutesPlans.unshift([qSubject, currentTime + spendTime, qTime])   
                }
            }
        } else {
        	// 다음 과제가 없는 경우
            answer.push(subject);
        }
    }
    
    answer.push(...stack.reverse().map((q) => q[0])); // stack에 있는 과제들을 차례로 넣어준다.
    return answer;
}

 

설명에 오류가 있거나 궁금한 부분이 있으면 언제든지 댓글로 달아주세요!

읽어주셔서 감사합니다.