문제

프로그래머스 - 기능개발

문제풀이

O(N)으로 풀어보자.

조건을 보아하니, 하나하나 시뮬레이션 해서 반복하는 것은 비효율적인 것 같다는 생각이 들었다.

따라서 다음과 같은 접근을 해보았다.

선행 배포가 우선되어야 한다.
각 작업은 작업률이 정해져있다.
앞선 작업이 끝나고 나면, 뒤의 완료된 작업도 배포한다. (묶음)

아무래도 3번에서 큐를 쓰라는 것 같았지만 (shift 해서 해당 날짜보다 작으면 하나씩 더하는 느낌으로)

직접 제대로 구현하는게 아닌 이상 shift()가 O(N)이기에 효율적일 것 같지 않다는 판단.

미리 계산해두면 이럴 필요가 없잖아!

미리 계산해버리기

남은 진도 (일수)는 문제에 나와있는 것 처럼 뽑아보려고 했다.

각 기능이 언제 100% (혹은 넘는지)를 판단하면 된다. 이를 map()을 활용하여 하나의 배열로 받아보자

const ends = progresses.map((progress, i) =>
  Math.ceil((100 - progresses[i]) / speeds[i])
);

배포는 그룹화

배포는 순서대로만 가능하다는 조건이 있었다.

미리 완성된다고 바로 배포되는 것이 아니다.

따라서 다음 조건을 고려해보자

현재 배포 기준일 : 앞선 기능이 완성된 날
새 기능의 완성일 <= 현재 배포 기준일 : 새 기능이 기준일 이내에 완성됐다면 묶여서 배포될 수 있다. -> count를 증가한다.
새 기능 완성일 > 현재 기준일 : 새 기능은 현재 배포 대상이 배포 된 후에도 완성되지 않음 => count를 answer에 넣은 후 새로운 기준일로 설정한다.

최종 코드

function solution(progresses, speeds) {
  var answer = [];

  // 한 번씩 시뮬하면 손해가 클 듯 하다.

  // 미리 언제 끝나는가를 계산하자
  // T1 예시 : [7, 3, 9]
  const ends = progresses.map((progress, i) =>
    Math.ceil((100 - progresses[i]) / speeds[i])
  );

  // 함수로 분리하는 것 보다, 명령형으로 하는게 편한 문제로 보인다.
  // 앞선 날 보다 뒤의 일정이 먼저 끝난다면 cnt를 증가시킨다.
  // 뒤의 일정이 나중에 끝난다면 cnt  + 1 => 집어넣기 => 뒤의 날이 바로 작업이 됨
  // 앞선 기능의 배포가 중요함

  // 첫 날 작업이 끝나는 데 걸리는 시간을 미리 넣는다.
  let curEndDay = ends[0];
  let cnt = 1; // 해당 배포는 미리 포함

  for (let i = 1; i < ends.length; i++) {
    // 첫 날 작업보다, 완성 시간이 빠르다면 배포 횟수가 1 증가한다.
    if (ends[i] <= curEndDay) {
      cnt += 1; // 개인적으로 후위 증가는 Rust 쓰듯 배제해보자.
    } else {
      // 앞선 일정보다 오래 걸린다.
      answer.push(cnt);
      curEndDay = ends[i];
      cnt = 1;
    }
  }
  answer.push(cnt);
  //

  return answer;
}

마무리 & 여담

O(N) 으로 판단된다…

미리 계산해두는 일수를 바탕으로 비교하며 그리디 처럼 풀어봤다.

이게 더 빠르겠지?

다만 생각하는데 걸린 시간은 시뮬보다 오래 걸린듯 한 느낌…

후위 증감을 사용하지 않은 이유

cnt +=1 을 사용한 이유

코드의 명확성을 조금 더 확보하기 위해서 해봤다.

cnt++ 보다 cnt += 1 이 더 명시적으로 보이기 때문.

또한 값의 사용 시점을 정확히 명시하는 편이 더 좋다고 생각하기에…

(남의 코드에서 ++가 나오고 또 해당 변수가 사용될 때 어질어질한 느낌이 있었으니까.)

for 문에서 쓴 이유는 익숙해서…

추가적으로 i가 확실히 증가하는 부분이 명시적이라는 판단도 있긴 했음.

Rust에서는 ++ 자체를 지원하지 않기에, 이유가 있지 않을까 했는데. 음.

이런 자료는 커뮤니티 관련해서 한 번 찾아서 정리해보면 도움이 되지 않을까 싶다.

어쨋든 코드는 내가 쓴 것을 여러 사람이 많은 시간에 걸쳐서 읽게 되는 것 이니까.

“읽는 사람을 위해 작성하자”

화이팅화이팅

-뱅-

[Node.js] 프로그래머스 - 기능개발

완료 일수 미리 계산 & Greedy

문제