[JS][백준]6068_시간 관리하기

문제 번호

6068번: 시간 관리하기

 

 

알고리즘 분류

• 그리디 알고리즘
• 정렬

 

문제 풀이

 표기된 난이도에 비해서 매우 쉬웠던 문제다. 

우선 입력받은 작업들을 마감시간이 빠른 순서로 정렬해준다.

function main(){
  let works = input.slice(1).map(_ => _.split(' ').map(Number));  // 필요시간, 마감시간.
  works.sort((a,b) => {
    let A = a[1];
    let B = b[1];
    if(A < B) return -1;
    else if(A > B) return 1;
    return 0;
  })  
  sol(works);
}

 

 이제 모든 작업이 마감시간 안에 끝날 수 있는지 판단해야 한다. 마감시간이 빠른 순서로 정렬해 두었기 때문에 작업에 소요되는 시간을 누적으로 더하면서 마감시간 이전에 끝낼 수 있는지 확인한다. 이 과정을 진행하면서 누적된 작업시간과 마감시간의 차이가 최소가 될 때를 기억해둔다. 이 값이 '존'이 최대한 늦게 일어날 수 있는 시간이다. 

 누적시간이 마감시간을 넘기면 해당 일들을 제때 진행할 수 없다는 뜻이다. 반대로 누적시간이 마감시간을 넘기지 않으면 누적시간과 마감시간의 차이만큼은 늦게 일어나도 된다. (눈뜨자마자 모든일을 연속해서 처리한다고 보자)

function sol(works){
  let answer = Infinity;

  let t = 0;
  for(let i=0; i<works.length; i++) {
    let [time, deadline] = works[i];
    t += time;
    if(t > deadline) return console.log(answer = -1);
    if(answer > deadline - t) answer = deadline - t
  }
  return console.log(answer);
}

 

전체 코드

/**
 * 먼저 끝내야 하는 순서로 정렬.
 */

const input = require('fs').readFileSync('input.txt').toString().trim().split('\n');
const N = +input[0];

function sol(works){
  let answer = Infinity;

  let t = 0;
  for(let i=0; i<works.length; i++) {
    let [time, deadline] = works[i];
    t += time;
    if(t > deadline) return console.log(answer = -1);
    if(answer > deadline - t) answer = deadline - t
  }
  return console.log(answer);
}
function main(){
  let works = input.slice(1).map(_ => _.split(' ').map(Number));  // 필요시간, 마감시간.
  works.sort((a,b) => {
    let A = a[1];
    let B = b[1];
    if(A < B) return -1;
    else if(A > B) return 1;
    return 0;
  })  
  sol(works);
}
main();

특이사항