[프로그래머스 Lv2] 과제 진행하기 - Javascript 풀이

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

프로그래머스

---

문제

끝내는 순으로 과제 이름이 담긴 배열을 반환하는 문제

 

생각

문제 설명에서 plans는 시간순으로 정렬이 안되어 있다는 것을 보았다.

그래서 배열을 시간순으로 정렬하는 것이 필요하겠다 생각했다. - 

문자열을 Date 객체로 변환해도 되지만, 나는 간단하게 문자열 비교 localeCompare 함수를 사용하였다.

 

1. 주어진 시간동안 현재 과제를 못 끝내는 경우

( = 과제의 시작 시간과 진행 시간을 더한 값이 다음 과제 시작 시간보다 클 경우 )

 

2. 주어진 시간에 현재 과제를 끝내는 경우

( = 과제의 시작 시간과 진행 시간을 더한 값이 다음 과제 시작 시간보다 작거나 같을 경우 )

 

크게 2가지 경우가 떠올랐고, 

못 끝낸 과제는 큐에 담아 관리하자고 생각했다.

 

문제풀이

localeCompare를 사용하여 배열을 시간순으로 정렬해준다.

 

1. 주어진 시간동안 현재 과제를 못 끝내는 경우 

 

현재 과제의 이름과 남은 시간을 큐에 저장해준다.

남은시간 = (현재시작 + 소요시간) - 다음시작

 

 

2. 주어진 시간에 현재 과제를 끝내는 경우

leftTime이 0일 때까지

큐에서 과제를 꺼내 남은 시간을 모두 소요해준다.

- 주어진 시간에 과제를 끝낼 수 있다면, 정답 배열에 과목 이름을 추가하고 leftTime을 남은 시간만큼 빼준다.

- 주어진 시간에 과제를 끝낼 수 없다면, 꺼낸 과목을 다시 큐에 push 해준다. 이때, 남은 시간은 leftTime을 뺀 값이다.

 

* 정답 배열에 큐에 남은 과목을 추가해준다.

 

• 마지막 과제 다음 과제가 없으므로, nextTime을 인위적으로 1540(=25시간 40분)으로 설정해주었다.
  ( 시작시간 제한 23:59, 최대 소요시간 100분 대비 )
• 하지만 실제로는 과제가 많이 밀릴 경우 25시간 40분 이후까지 갈 수 있으므로,
  큐에 남은 과제가 있다면 그 처리까지 고려해야 한다.

 

* 다른 방법 ) 대충 nextTime을 100000 같이 큰 숫자로 설정하면, queue배열을 추가로 붙이지 않아도 된다.

- 대충 최대 시간이 24 x 60 + 100 x 1000 = 101,440이니까 100,000 설정

- 10,000으로 설정하면 실패하는 케이스 존재 ! 

const nextTime = i !== plans.length-1 ? getStartTime(plans[i+1]) : 100000

.
.
.
return answer

 

 

코드

function getStartTime(task) {
    const [h, m] = task[1].split(':').map(Number)
    return h*60 + m
}

function solution(plans) {
    let queue = []
    let answer = []
    
    plans.sort((a, b) => a[1].localeCompare(b[1]))
    
    for(let i=0; i<plans.length; i++) {
        const curTime = getStartTime(plans[i])
        const nextTime = i !== plans.length-1 ? getStartTime(plans[i+1]) : 1540
        const playtime = Number(plans[i][2])
        
        if ( curTime+playtime > nextTime ) { // 현재 과제를 다 못 끝낼 경우
            // 남은 과제 시간 계산해서 큐에 저장
            queue.push([plans[i][0], curTime+playtime-nextTime])
        } else { // 시간이 같거나 남는 경우
            answer.push(plans[i][0])
            
            let leftTime = nextTime - (curTime+playtime) // 남은 시간
            
            while( leftTime > 0 ) {
                const prevTask = queue.pop()
                if ( !prevTask ) break
                
                if ( prevTask[1] <= leftTime ) {
                    answer.push(prevTask[0])
                    leftTime = leftTime - prevTask[1]
                } else {
                    queue.push([prevTask[0], prevTask[1]-leftTime])
                    break
                }
            }
        }
    }
    
    // 큐에 남아있는 과목도 추가해주기 ( 최근 멈춘 순서 )
    return answer.concat(queue.reverse().map((e) => e[0]))
}