[프로그래머스] 기능개발 (Lv. 2, JavaScript)

📝 문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/42586

프로그래머스

목표: 배포되어야하는 순서대로 적힌 작업 배열 progresses 와 개발 속도가 적힌 정수 배열 speeds 주어지면 각 배포마다 몇 개의 기능이 배포되는지를 반환해야한다.

핵심조건

• 작업 진도가 100%가 되어야 배포를 진행할 수 있다.
• 작업의 개수는 100개 이하 및 작업 진도는 100 미만, 속도는 100 이하이다.
• progresses 배열에서 뒷 작업이 먼저 끝나더라도 배열의 제일 앞 작업이 끝나야 배포가 진행된다.
• 배포는 하루에 한 번만 가능하다.
• 각 작업들은 다른 작업 진행에 영향받지 않고 병렬적으로 처리된다.

---

🔍 풀이 과정 (나만의 풀이 전략)

우선 배열에서 첫 번째 요소부터 작업이 끝나기 위해 필요한 날짜 계산이 필요할 것 같다.

 

progresses	speeds	return
[93, 30, 55]	[1, 30, 5]	[2, 1]

위와 같이 주어졌을 때 progresses의 첫 번째 작업이 끝나기 위해 필요한 기간은

100% - 93%(현재 진행률) = 7%, 이는 총 4일이 소요된다.

그럼 4일동안 작업이 진행되었을 때 첫 번째 작업의 뒷 순서의 작업들의 진행률을 계산해보자

30 + 30 * 4 = 150%, 55 + 5 * 4 = 75 으로 첫 번째 작업이 완료되고 배포될 때 두번째 작업 역시 배포되어야한다.

 

이런 방식으로 계산한다면 다음 테스트 케이스의 경우에도

progresses	speeds	return
[95, 90, 99, 99, 80, 99]	[1, 1, 1, 1, 1, 1]	[1, 3, 2]

첫 번째 작업이 끝나기 위해 필요한 기간은

100% - 95% = 5%, 총 5일이 소요된다.

그럼 모든 작업들의 작업률은 다음과 같다.

[100, 95, 104, 104, 85, 104]

여기서 첫 번째 작업은 완료되었으므로 배포를 진행한다.

그런데 두 번째 작업은 아직 95%로 완료되지 않았으므로, 3,4,6번째 작업이 완료되었지만 배포는 진행하지 않는다.

따라서 5일차에는 하나의 작업만 배포를 진행하고

 

다시 5일 뒤에 작업률은

[100, 109, 109, 90, 109] 으로 3개의 작업이 배포될 것이다.

그리고 다시 10일 뒤에

[100, 119]으로 2개의 작업이 배포되는 것이다.

 

이러한 접근법에 따라 문제 해결을 위해서 다음과 같은 반복 시퀀스를 진행한다.

1. progresses 배열의 첫 번째 작업이 완료되기 위해 필요한 기간을 계산한다.
2. progresses 배열의 작업들의 진도에 작업속도 * 위에서 계산한 기간 만큼 더한다.
3. 여기서 progresses 배열이 비어있을 때까지 순회
   1. progresses 배열의 첫 번째 작업 진도가 100 이상이라면 배포 카운트를 +1 하고, progresses와 speeds 배열의 첫 번째 항목을 제거한다.
   2. 첫 번째 작업 진도가 100 미만이라면 순회 종료 (break)
4. answer 배열에 배포 카운트를 push 한다.
5. progresses 배열이 빌 때까지 1-4 과정을 반복

🛠️ 트러블슈팅

처음 제출한 코드는 반복 시퀀스의 3번 과정을 진행할 때 while문이 아닌 for문을 사용했었다.

for (let i=0; i < progresses.length; i++) {
      if (progresses[0] >= 100) {
          deployCount++;
          progresses.shift();
          speeds.shift();
      } else {
          break;
      }
  }

이 경우 오답이라고 채점되었는데, 이는 for문과 while문의 동작방식의 차이를 이해하지 못한 부분에서 발생한 문제였다.

• for (let i=0; i < progresses.length; i++) 루프가 시작되고
• 만약 if (progresses[0] >= 100) 조건이 참이된다면 배열의 첫 번째 요소를 제거 (shift)하게 된다. 이렇게 된 후에 배열의 모든 요소들이 앞으로 한 칸씩 당겨지게 된다.
• 하지만 루프가 다음 회차로 넘어가면 i는 1이 된다.
• 이 때 문제는 i번 인덱스 값은 루프가 돌때마다 1씩 증가하는데, 루프의 종료 조건인 i < progresses.length; 는 점점 작아지게 되면서 의도와 맞지 않게 동작하게 된다.

예를 들어

progresses = [100, 100, 100] 인 경우에

• i = 0일 때 progresses[0]은 100이므로, 조건문이 참이므로 deployCount를 상승시키고 두 배열을 shift() 한다. 배열은 [100, 100] 이 된다.
• i = 1일 때, progresses.length = 2이므로 마찬가지로 조건문을 통과하고 shift() 하면 배열은 [100]이 된다.
• i = 2일 때, progresses.lengh = 1 이므로 배열에 아직 [100] 으로 100이 남아있는데도 루프르 종료해버려서 잘못된 deployCount가 계산이 된다.

따라서 인덱스 i를 사용하지 않는 while (progresses.length > 0) 문을 사용해야 shift()를 해서 배열의 길이가 줄어들더라도 문제가 생기지 않는다.

---

💻 코드 (Code)

function solution(progresses, speeds) {
    let answer = [];
    while (progresses.length > 0) {
        let deployCount = 0;
        let day = 0;
        day = Math.ceil(((100 - progresses[0]) / speeds[0]))
        
        for (let i=0; i < progresses.length; i++) {
            progresses[i] = progresses[i] + speeds[i] * day;
        }
        while (progresses.length > 0) {
            if (progresses[0] >= 100) {
                deployCount++;
                progresses.shift();
                speeds.shift();
            } else {
                break;
            }
        }

        answer.push(deployCount);
    }
    return answer;
}

최적화된 코드

function solution(progresses, speeds) {
	let answer = [];
	let days = progresses.map((p, i) => Math.ceil((100 - p) / speeds[i]));
	
	let maxDay = days[0];
	let count = 1;
	
	for (let i = 1; i < days.length; i++) {
		// 기준일보다 빨리 작업이 끝났다면 배포
		if (days[i] <= maxDay) {
			count++;
		} else {
			// 기준일보다 오래걸리면 이전까지 쌓인 기능 배포 후에 기준일을 갱신한다.
			answer.push(count);
			count = 1;
			maxDay = days[i];
		}
	}
	answer.push(count); // 마지막 남은 그룹 추가
	
	return answer;
}

진행 상황을 매번 shift()하고 업데이트 하는 방법 대신, 각 기능이 완료되는데 소요되는 기간을 먼저 계산한 후 배열을 한 번만 순회하는 방법으로 해결이 가능하다.

이 방법의 경우 원본 배열을 수정하는 작업이 없기 때문에 더 빠른 성능을 보인다.

---

❓ 꼬리 질문 및 복습 (Self-Q&A)

복습

이 문제가 왜 스택/큐 문제인지

• 문제의 핵심은 먼저 들어온 작업이 끝난 후에 배포되면서 먼저 나가아한다는 점이므로, 큐의 핵심 원리인 FIFO를 담고있는 문제이다. 뒤의 작업이 아무리 빨리 끝나더라도 큐의 앞의 작업이 나갈 때 까지 나갈 수 없다는 점이 문제의 핵심.

JS의 Array 인스턴스의 주요 메서드들

요소 추가 및 제거

• push(…items): 배열의 끝에 요소를 추가하고 변경된 길이를 반환하는 메서드.
• pop(): 배열의 끝 요소를 제거하고,그 요소를 반환하는 메서드
• unshift(…items): 배열의 앞에 요소를 추가하는 메서드
• shift(): 배열의 앞 요소를 제거하는 메서드. 제거한 후 나머지 요소들을 앞으로 당기는 작업이 포함
• splice(start, deleteCount, …items): 특정 위치의 요소를 제거하거나, 교체/추가하는 메서드

순회 및 탐색

• forEach(callback): 배열의 각 요소에 대해 함수를 실행하는 메서드.
• map(callback): 배열의 각 요소에 함수를 적용하여 새로운 배열을 생성하는 메서드.
• filter(callback): 조건에 맞는 요소만 추려서 새로운 배열을 생성하는 메서드.
• reduce(callback, initValue): 배열을 순회하며 하나의 결과값을 만드는 메서드.
• find(callback) / findIndex(callback): 조건에 맞는 첫 번째 요소나 그 인덱스를 반환하는 메서드.

배열 변형 및 정렬

• sort(compareFunc): 배열을 정렬하는 메서드.
• reverse(): 배열의 순서를 뒤집는 메서드.
• slice(start, end): 배열의 일부분을 복사하여 새로운 배열을 생성하는 메서드.
• join(seperator): 배열의 모든 요소를 문자열로 합치는 메서드.
• concat(): 두 개 이상의 배열을 병합하여 새로운 배열을 반환하는 메서드.

논리 판단 메서드

• includes(value): 배열이 특정 값을 포함하는지 여부를 반환하는 메서드.
• every(callback): 배열의 모든 요소가 조건을 만족하는지 여부를 반환하는 메서드.
• some(callback): 배열에서 하나라도 조건을 만족하는지를 반환하는 메서드.

꼬리질문

• Q. shift() 메서드 대신 성능을 개선할 방법이 또 있을까?
  • 배열의 인덱스를 가리키는 pointer 변수를 만들어서 실제 요소를 지우는 방법 대신 포인터 인덱스만 옆으로 옮겨가며 검사하는 방법

---

💬 마무리하며

이번에는 답 먼저 보지않고 해결한 문제였습니다… 휴

다만 성능 면에서는 shift() 메서드는 배열에서 항목을 제거하고 나머지 항목들을 다 앞으로 당기는 작업이 포함되기 때문에 O(N)의 시간 복잡도를 가지기 때문에 최악의 경우에 O(N^2)의 시간복잡도를 가지는 문제가 존재한다는 점이 아쉬운 해결 방안이었습니다. 또한, for문의 경우 shift() 메서드를 사용할 경우 배열의 원본이 수정되기 때문에 i 인덱스가 일치하지 않는 문제를 고려하지 않아 해결 시간이 더 걸렸던 문제였습니다.

이런 부분들이 아쉬웠던 것 같습니다.