알고리즘/프로그래머스 - JS

[프로그래머스] level.2 기능개발

개발자성장기 2023. 5. 19. 14:23
반응형

 

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 


나의 풀이 

이 문제를 3번째 풀면서 복습하고 있다 

매번 풀때마다 풀이가 바뀐다는게 신기하다.

 

풀이 1

function solution(progresses, speeds) {
  let countBox = [];
  let completeBox = [];
  for (k = 1; k < 100; k++) {
    let complete = [];
    for (i = 0; i < progresses.length; i++) {
      if (typeof progresses[i] == 'number') progresses[i] += speeds[i];
      if (progresses[i] >= 100) {
        complete.push([i, k]);
        progresses.splice(i, 1, 'end');
      }
    }
    if (complete[0] != null) completeBox.push(...complete);
  }
  completeBox.sort((a, b) => a[0] - b[0]);

  console.log(completeBox);
  let count = 0;
  completeBox.reduce(
    (acc, cur, i) => {
      if (acc[0] < cur[1]) {
        if (i) countBox.push(count);
        acc[0] = cur[1];
        count = 0;
        count++;
      } else {
        count++;
      }
      if (completeBox.length == i + 1) countBox.push(count);
      return acc;
    },
    [0]
  );
  return countBox;
}

아주 옛날에 풀었던 풀이인데 굉장히 복잡해보인다. 

이렇게 푸는건 비추한다. 

completeBox는  이중배열로 이루어져있다.  

[[ index, 완료되는데 걸리는 일수] , [ index, 완료되는데 걸리는 일수], ....] 

이런식으로 이루어져있고 completeBox.reduce에서 그것을 토대로 count를 계산한다. 

이 풀이는 진짜 아닌것 같다. 

 

풀이 2

function solution(progresses, speeds) {
  const result = [];
  // 각 요일 마다 배포 가능한 개수
  let deployCount = 0;
  // 배포되는데 필요한 일수
  let maxDay = Math.ceil((100 - progresses[0]) / speeds[0]);

  for (let i = 0; i < progresses.length; i++) {
    // 개별 작업의 배포되는데 필요한 일수
    const day = Math.ceil((100 - progresses[i]) / speeds[i]);

    // 앞 작업에서 배포에 필요한 일수보다 뒷작업의 일수가 더 적으면 함께 배포된다.
    if (day <= maxDay) {
      deployCount++;
    } else {
      // 앞 작업에서 배포 일수를 충족하였는데 뒷 작업이 배포 할 수 없는 상황일 때
      result.push(deployCount);
      deployCount = 1;
      maxDay = day;
    }
  }

  result.push(deployCount);
  return result;
}

이 풀이는 다른 사람풀이를 보다가 maxDay 부분을 계산하는게 너무 참신해서 해당부분을 토대로 문제를 풀어봤다. 

 

1. progresses 의 첫번 째 index의 배포되는데 필요한 일수를 maxDay로 고정시켜놓고 

2. for 문을 통해서 각각 배포되는데 몇일이 걸리는지 확인하고

3. maxDay 와 day를 비교해서 maxDay 보다 day가 작으면 같이 배포되는 것이고 day가 더 크면 따로 배포되는 것으로 분류된다. 

 

시간 복잡도도 낮고 좋은 것 같다. 

 

풀이 3

function solution(progresses, speeds) {
  const result = []
  while(progresses.length) {
      
      for(let i =0; i<progresses.length; i++) {
      progresses[i] += speeds[i]
      }
      
      let count = 0
      while(progresses.length >0 && progresses[0] >= 100) {
          progresses.shift()
          speeds.shift()
          count += 1
      }
      if(count > 0) result.push(count)
      
      
      
      
  }
  return result
}

 

풀이 2보다 시간복잡도가 훨씬 올라갔다. 

해당 풀이는 하루를 보내고 progresses를 확인하고 또 하루를 보내고 progresses를 확인해서  progress가 100이 넘으면 count + 1을 하고 배열에서 빼는식으로 푸는 방식이다. 

 

이와 비슷한 풀이는 아래와 같다. 

 

풀이 4

function solution(progresses, speeds) {
  const result = []
  while(progresses.length) {
      for(let i =0; i<progresses.length; i++) {
      progresses[i] += speeds[i]
      }
      if(progresses[0] >= 100) {
          let imcomplete = progresses.findIndex((progress) => progress < 100)
          if(imcomplete === -1){
              result.push(progresses.length)
              return result
          }
          progresses.splice(0, imcomplete)
          speeds.splice(0,imcomplete)
          result.push(imcomplete)
      }
      
  }
  return result
}

 

이 풀이 역시 비슷하지만 findIndex를 사용해서 progresses[0]이 100을 넘겼을 때  100을 넘지 않는 부분을 찾아서 그 전까지 제거를 하고 result에 넣는 방식이다. 

 

 

네 가지 풀이중 2번풀이가 제일 괜찮은것 같다.  

다음에 다시 풀면 또 다른 풀이로 풀 것 같다. 

 

 

반응형