기능 개발

YEONGHUN KO·2021년 11월 26일
0

ALGORITHMS - PRACTICE

목록 보기
20/50
post-thumbnail

1. 기능 개발

프로그래머스에서 코딩테스트를 공부하고 있다. 자주 나오는 문제 위주로 풀고 있는데 그 중에 하나가 '기능개발' 문제이다.
progesses와 speed 배열 두개가 주어진다. 그리고 하루가 지날 때 마다 speed 만큼 progress가 이루어진다. 그러나 n번째 작업은 n-1번째 작업이 완료되어야 비로소 출시가 된다. 예를 들어 아래와 같은 progress, speed 배열이 주어진다고 하자.

[93, 30, 55] [1, 30, 5] 이때 첫번째 작업(93%완료된)이 끝나는 날은 7일이 되어서이다. 7일째 되는날 두번째 작업의 완료도는 240%(30+30*7) 이므로 완료되고도 남았다. 반면 3번째 작업의 완료도는 90%(55+5*7)이므로 아직 남았다. 그래서 7일째에 1,2번째 작업이 끝나므로 answer에는 2가 추가된다. 그리고 9일째 되는날 3번째 작업이 끝나므로 answer에 1이 추가되어서 최종 return 값은 [2,1] 이 된다!

2. 접근 방법

큐이므로 완료 될때마다 앞에서 하나씩 없어지면 된다고 생각했다.

  • pseudo code
    • progress 의 첫번째 원소를 speed의 첫번째 원소와 더해나간다
    • 첫번째 원소를 더해가면서 두번째 새번째 원소도 함께 더해가야한다.
    • 첫번째 원소를 더해갔을때 100이 되었을때 progress안에 있는 그 뒤에 원소들도 체크한다.
    • 그 뒤에 있는 원소들도 100이 되었거나 그 이상이면 shift 한다. 100이 되면 100이 될때마다 카운트한다.
    • 그리고 100이 안된 지점까지 카운트를 한다.
    • 카운트를 answer에 넣고 count는 초기화.
    • 100이 안된지점으로 돌아가서 그 progress지점부터 뒤의 지점까지 다시 일을 진행한다.
    • 100이 되었을 때 카운트를 하고 그 뒤의 작업을 본다. 100이 완료된 지점까지 카운트를 하고 다시 answer에 넣는다.
    • 위의 과정을 반복한다. progress에 아무것도 남지 않을 때 까지.
      • 관건은, 100이 되는 시점을 잘 파악해서 그 바로 뒤에 완료된 작업들을 모두 카운트를 하는 것이다.

일단 요렇게 짜보았다.

function solution(progresses, speeds) {
  var answer = [];
  let tmp = [];
  let days = 0;
  let count = 0;

  while (progresses.length) {
    // improving functions
    for (let i = 0; i < progresses.length; i++) {
      console.log("----------accumulated----------");
      progresses[i] += speeds[i];
      console.log(progresses, count);
    }

    // check to see if there is any functions you can release.
    if (progresses[0] >= 100) {
      for (let j = 0; j < progresses.length + 1; j++) {
        if (progresses[0] >= 100) {
          ++count;
          console.log("-----------100!!------------");
          console.log(progresses, count);
          // 작업이 완료되면 speed도 같이 제거한다.
          progresses.shift();
          speeds.shift();
          continue;
        }
      }
    }

    if (count) {
      answer.push(count);
      count = 0;
    }

    console.log(`-------------${++days}day passed-------------`);
  }

  return answer;
}

그런데 역시나 제야의 고수분이 계셨다. 그래서 그 코드를 공유해보려고 한다.

3. 다른 답안

이분의 로직은 아래와 같다

  • pseudo code
    • progress와 speed를 통해서 완료될때까지 며칠을 기다려야할지 계산한다음 각각 days 배열에 담는다.
    • 그리고 days를 loop하면서 n이 n+1.. 보다 크면 완료된 숫자를 계속 더해간다. n보다 더 큰 수가 나올때 까지 - 큰 수가 나오면 다시 새로운 1을 추가한다
      와... 이 얼마나 간단한가. 관건은, 한 번에 days를 계산하고 days를 가지고 출시될 수 있는 기능을 계산해 나가는 것이다.
function otherSolution(progresses,speed) {
  let answer = [0]
  let days = progresses.map((func,index) => {
    return Math.ceil((100-func)/speed[index]))
  })

let max = days[0]

  for(let i = 0 ,j = 0 ; i<days.length;i++) {
    if(max >= days[i]) {
      answer[j] += 1
    } else {
      max = days[i]
      answer[++j] = 1
    }
  }

  return answer
}

끝!!

profile
'과연 이게 최선일까?' 끊임없이 생각하기

0개의 댓글