[Programmers] 과제 진행하기 - Javascript

INDEX

https://school.programmers.co.kr/learn/courses/30/lessons/176962#

프로그래머스

 

 

Solution

우선 시간문제에선 저는 시간을 분 단위로 변환하고 시작합니다. 시간 개념으로 해석하려면 60분 다음엔 시간을 올려줘야 해서 번거롭기 때문에 아예 분 단위로 고려하는 것이 편합니다.  "15:30" 이 주어진다 면 930이 반환됩니다.

function timeToMinute(time) {
  return Number(time.split(":")[0] * 60) + Number(time.split(":")[1]);
}

그리고 시간 계산을 편하게 하기 위해 파라미터로 받는 과제원소를 변환해 주는 함수도 작성합니다.

function convertTimeArrayToNumber(arr) {
  return [arr[0], timeToMinute(arr[1]), Number(arr[2])];
}

["영어", "15:30", "30"] 이 주어진 다면 ["영어", 930, 30] 이 반환됩니다. 사전 준비는 마쳤으니 알고리즘을 짜보도록 합니다.

 

포인트는 이전 과제가 마쳤을 때 새로운 과제가 주어진 다면 새로운 과제부터! 합니다. 이 말은 즉 Stack 구조라는 뜻입니다. 나중에 부여받은 과제부터 해야 하기 때문에 First In, Last Out 이 됩 니다. 

우선 Solution 부터 보면 

function solution(plans) {
  //시간 순서대로 정렬합니다.
  plans = plans.sort((a, b) => timeToMinute(a[1])-timeToMinute(b[1]));
  let answer = [];
  let workStack = [convertTimeArrayToNumber(plans[0])];
  let updateTimeWorkStack = [];
  for (let i = 1; i < plans.length; i++) {
    const newWork = convertTimeArrayToNumber(plans[i]);
    const [nWork, nSTime, nSpend] = newWork;
    const newWorkDoneTime = nSTime + nSpend;

    while(workStack.length){
        const [lWork, lSTime, lSpend] = workStack.pop();
        const lastWorkDoneTime = lSTime + lSpend; //마지막 과제의 끝나는 시간

        if (lastWorkDoneTime > nSTime) { //새롭게 받은 과제의 시작시간보다 스택에 쌓인 과제의
        //끝나는 시간이 더 크면 스택에 쌓인 과제들의 시간을 바꿔준다.
            updateTimeWorkStack.push([lWork, newWorkDoneTime, lSpend - (nSTime-lSTime)]) //(1)
        }else{
            answer.push(lWork);
        }
    }
    while(updateTimeWorkStack.length){workStack.push(updateTimeWorkStack.pop())}
    workStack.push(newWork);//(2)
  }

  while(workStack.length){answer.push(workStack.pop()[0])}
  return answer;
}

그림과 함께 볼까요?

예제 중 제일 복잡한 아래 예재로 해보겠습니다.

[["science", "12:40", "50"], ["music", "12:20", "40"], ["history", "14:00", "30"], ["computer", "12:30", "100"]] //시간 순으로 정렬하면 [["music", "12:20", "40"],["computer", "12:30", "100"],["science", "12:40", "50"],["history", "14:00", "30"]]

반복문을 시작 전엔 workStack 에 다음과 같이 있을 겁니다.

처음 반복문 (i===1) 일 땐 주어진 과제 computer의 시작시간(750)이 music의 끝나는 시간(780) 보다 작기 때문에 새로운 과제 computer를 시작합니다. 아직 music 이 끝난 게 아니니 workStack에 다시 쌓아야 겠죠. 하지만, music은 computer 과제를 시작하기 전까지 10분동안 진행을 했고, 30분이 남았습니다. 다시 music 을 시작하는 시점은 computer 가 끝나는 시점인 850이 됩니다. 따라서 시간을 변경해주어야 합니다. Solution함수의 주석 중 (1) 번이 위 그림에서 (1)을 나타냅니다. updateTimeStack 변환된 시간을 담고 다시 workStack 에 쌓아줍니다.

 

 

다음 반복문 (i===2)를 보면 과제 science 또한 이전 과제인 computer 가 끝나기도 전에 시작합니다.

그럼 computer의 시작시간은 다시 science의 끝나는 시간인 810, 남은 시간은 10분을 진행했으므로 90입니다.

그리고 music 도 science에게 우선권을 뺏겼습니다. music의 시간도 변경해줍니다. music 의 시작 시간은 역시 science가 끝나는 시간인 810, 진행 시간은 남았던 시간 30 + computer 과목이 끝날 때까지 기다린 시간 90 해서 120입니다. 

 

*왜 music의 진행시간이 늘어날까요? 

- music 은 science 과목으로 인해 시작시간이 810으로 변경됐습니다. 하지만 computer 과목을 진행해야 되기 때문에 computer 과목이 끝날 때까지 기다려야 합니다. 상식대로라면 music 은 computer 가 끝나는 시점인 900에 시작해서 남은 30분을 소요하도록 시간이 변경되어야 하지만 중요한 건 끝나는 시점이기 때문에 영 향은 없습니다. 

 

다음 반복문 (i===3)를 보면 과제 history는 science 가 끝나는 시점보다 뒤인 840에 시작합니다. 따라서 science를 가장 먼저 마칠 수 있습니다. 이후 computer와 비교를 해보니 computer의 끝나는 시간 900 보다 history 가 먼저 시작하기 때문에 우선권을 history에게 내줍니다.

 

computer는 science가 끝난 시점(810)부터 history가 시작하는 시점 (840)까지 진행했으니 남은 진행시간은 60이 됩니다. 또한 music은 아까 computer가 끝날 때까지 기다리는 시간을 더해줬으니 이젠 computer를 진행한 시간을 빼줘야겠죠.

120에서 30을 빼줍니다.

 

이제 더 이상 고려할 과제가 없습니다. 제일 먼저 마친 science 과목과 남은 과제를 순서대로 뽑아서(pop) 정답으로 반환하면 됩니다.

while(workStack.length){answer.push(workStack.pop()[0])}
return answer;

 

전체코드

function solution(plans) {
  //시간 순서대로 정렬합니다.
  plans = plans.sort((a, b) => timeToMinute(a[1])-timeToMinute(b[1]));
  let answer = [];
  let workStack = [convertTimeArrayToNumber(plans[0])];
  let updateTimeWorkStack = [];
  for (let i = 1; i < plans.length; i++) {
    const newWork = convertTimeArrayToNumber(plans[i]);
    const [nWork, nSTime, nSpend] = newWork;
    const newWorkDoneTime = nSTime + nSpend;

    while(workStack.length){
        const [lWork, lSTime, lSpend] = workStack.pop();
        const lastWorkDoneTime = lSTime + lSpend;

        if (lastWorkDoneTime > nSTime) {
            updateTimeWorkStack.push([lWork, newWorkDoneTime, lSpend - (nSTime-lSTime)])
        }else{
            answer.push(lWork);
        }
    }
    while(updateTimeWorkStack.length){workStack.push(updateTimeWorkStack.pop())}
    workStack.push(newWork);
  }

  while(workStack.length){answer.push(workStack.pop()[0])}
  return answer;
}
function timeToMinute(time){
    return Number(time.split(":")[0]*60) + Number(time.split(":")[1]);
}
function convertTimeArrayToNumber(arr){
    return [arr[0], timeToMinute(arr[1]), Number(arr[2])];
}