프로그래머스 기능개발

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

문제 풀이

stack 자료구조를 이용해 접근

1. 가장 앞을 기준으로 완료를 해야 뒤에 있는 것들도 처리가 가능하므로 가장 앞에 있는 것을 shift() 하여 남은 일 수 검사

2. 남은 일 수 만큼 나머지 progress 들도 남은 일 수 * speed만큼 더해줌

3. 가장 앞의 progress를 완료했을 때 뒤이어 완료할 수 있는 progress에 대해서 전부 꺼내줌

4. 최종적으로 count를 answer에 push 해주면 됨

function solution(progresses, speeds) {
    let answer = [];
    
    while (progresses.length > 0) {
        let [progress, speed] = [progresses.shift(), speeds.shift()];
        let remaining_progress = 100 - progress;
        let remaining_days = remaining_progress % speed === 0 ? remaining_progress / speed : Math.floor(remaining_progress / speed) + 1;
        let count = 1;
        
        for (let i = 0; i < progresses.length; i++) {
            progresses[i] += speeds[i] * remaining_days;
        }        
        
        while (progresses[0] >= 100) {
            count += 1;
            progresses.shift();
            speeds.shift();
        }
        
        answer.push(count);
    }
    
    return answer;
}

---

결론

1. 남은 날 수 계산 개선

• progress가 speed에 나누어 떨어지지않으면 다음 날 완료가 되니 + 1을 하도록 삼항연산자를 사용해 구했음
• Math.ceil()이라는 반올림 메서드를 이용하면 위와 같은 처리가 필요없음

// let remaining_days = remaining_progress % speed === 0 ? remaining_progress / speed : Math.floor(remaining_progress / speed) + 1;

let remaining_days = Math.ceil(remaining_progress / speed);

---

다른 사람의 풀이 O(n)

• 먼저 progress들에 대한 남은 일 수를 계산해서 저장을 하고
• 기준이 되는 날(maxDay)을 기준으로 해당 날보다 적게 남은 progress들은 모두 배포가 가능하므로 +1을 해줌
  • 만약 더 크다면 기준을 바꿔 다시 검사하도록 수행

function solution(progresses, speeds) {
    let answer = [0];
    let days = progresses.map((progress, index) => Math.ceil((100 - progress) / speeds[index]));
    let maxDay = days[0];

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

    return answer;
}