42586. 기능 개발

프로그래머스 42586번 풀이

이 글은 Obsidian에서 마이그레이션되었으며, 그 과정에서 AI의 도움을 받았습니다. 오류나 누락된 내용이 있다면 댓글로 알려주세요!

문제

코딩테스트 연습 - 기능개발 | 프로그래머스 스쿨

풀이

아이디어

배포는 앞에서부터 순차적으로 이루어진다는 것이 중요했다. 뒤쪽 기능이 먼저 완료될 수 있더라도 일단 앞쪽 기능을 먼저 완료시켜야 했다.

1. 날짜를 1일씩 증가시키며 각 날짜에 완료 가능한 작업들을 확인한다.
2. 현재까지 배포된 작업 다음 것부터 순차적으로 체크한다.
3. 작업 진도가 100 이상이 되는 작업들은 연속으로 세어준다.
4. 만약 진도가 100 미만이 되는 작업이 있다면 세는 것을 중단한다. (어차피 뒤 작업들 모두 배포 못함)
5. 완료된 작업이 있다면 배포하고 개수를 기록한다.

각 날짜마다 진도 + (속도 × 경과일수) 로 현재 진행도를 매번 계산해서 별도로 진행도 배열을 관리하지 않아도 되게 했다.

코드

function solution(progresses, speeds) {
  let answer = [];
  let currentDay = 1;
  let deployCount = 0;

  while (deployCount < progresses.length) {
    let completedCount = deployCount;
    // 작업
    while (completedCount < progresses.length) {
      if (
        progresses[completedCount] + speeds[completedCount] * currentDay <
        100
      )
        break;
      completedCount++;
    }
    // 배포
    if (deployCount !== completedCount) {
      answer.push(completedCount - deployCount);
      deployCount = completedCount;
    }
    currentDay++;
  }

  return answer;
}

시간 복잡도

• 시간 복잡도: 최악의 경우 모든 작업이 하루에 하나씩 완료된다면 O(N × D) (N은 작업 수, D는 최대 소요 일수)가 된다. 하지만 작업 개수, 작업 진도, 작업 속도가 모두 100 이하의 값들이기 때문에 괜찮았다.