프로그래머스 42586 - 기능 개발

오답

#include <string>
#include <vector>
#include <queue>

using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;
    
    vector<int> endDate;
    
    for (int i = 0; i < progresses.size(); i++) { // O(N)
        int days = (100 - progresses[i]) / speeds[i];
        
        if ((100 - progresses[i]) % speeds[i] != 0)
            days++;
        
        endDate.push_back(days);
    }
    
    int cur = 0;
    
    while (cur < endDate.size()) {
        cur = 0;
        
        for (int next = cur + 1; next < endDate.size(); next++) {
            if (endDate[next] <= endDate[cur])
                cur++;
            else {
                break;
            }
        }
        
        if (cur + 1 == endDate.size()) {
            answer.push_back(1);
            break;
        } else {
            answer.push_back(cur + 1);
        }
    }
    
    return answer;
}

💭 풀이

1. 개발 완료까지 소요되는 일수 계산 후 배열(endDate)에 저장
   • (100 - 진행률) / 개발 속도
   • 나머지가 있으면 일수 + 1

2. 앞에서부터 뒤쪽 원소들 중에 작은 것까지의 index + 1를 반환
   • endDate[0]부터 시작해서 현재 cur이 가리키고 있는 원소보다 작을 때까지 cur을 증가시킴
   • 현재 원소보다 크면 반복문 종료
   • ex) {4, 3, 5, 6, 5, 4}
     → {4, 3} ⇒ 2
     → {5} ⇒ 1
     → {6, 5, 4} ⇒ 3

💥 문제점
while 반복문 조건이 cur이 증가하면서 endDate 배열의 끝까지 순회하고 끝나야 하는데, 마지막 인덱스가 바로 전 인덱스보다 큰 경우 (즉, 마지막 하나만 배포하면 되는 경우) cur++를 수행하지 않고 break 되기 때문에 무한루프에 빠짐

---

정답

#include <string>
#include <vector>
#include <queue>

using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;
    
    vector<int> endDate;
    
    for (int i = 0; i < progresses.size(); i++) { // O(N)
        int days = (100 - progresses[i]) / speeds[i];
        
        if ((100 - progresses[i]) % speeds[i] != 0)
            days++;
        
        endDate.push_back(days);
    }
    
    int cur = 0;
    int next = cur + 1;

    while (cur < endDate.size()) { // O(N)
        if (cur == endDate.size() - 1) {
            answer.push_back(1);
            return answer;
        }

        int cnt = 1;
        for (next = cur + 1; next < endDate.size(); next++) { // O(N)
            if (endDate[next] <= endDate[cur])
                cnt++;
            else {
                break;
            }
        }
        cur = next;
        
        answer.push_back(cnt);
    }
    
    return answer;
} // O(N^2)

💭 풀이

1. 개발 완료까지 소요되는 일수 계산 후 배열(endDate)에 저장
   • (100 - 진행률) / 개발 속도
   • 나머지가 있으면 일수 + 1

2. 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포 되어야 하기 때문에 앞에서부터 뒤쪽 원소들 중에 작은 것들의 원소 개수를 count
   • ex) {7, 3, 9} -> 7부터 3까지 배포,
   • endDate의 0부터 시작해서 현재 cur이 가리키고 있는 원소보다 작을 때까지 cur을 증가시킴

---

다른 사람 풀이

#include <string>
#include <vector>
#include <iostream>

using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;

    int day;
    int max_day = 0;
    for (int i = 0; i < progresses.size(); ++i)
    {
        day = (99 - progresses[i]) / speeds[i] + 1;

        if (answer.empty() || max_day < day)
            answer.push_back(1);
        else
            ++answer.back();

        if (max_day < day)
            max_day = day;
    }

    return answer;
}

💡

day = (99 - progresses[i]) / speeds[i] + 1;

이렇게 하면 나머지가 있는 경우에도 자동으로 올림 처리가 되어 나눠 떨어지는지 아닌지 여부를 확인하지 않아도 됨,,, 충격

• progresses[i] == 100인 경우, (99 - 100) / speeds[i] + 1은 -1 + 1 = 0이 되므로, 진행률이 100인 경우는 따로 예외 처리가 필요할 수 있음