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

이 문제를 옛날에 자바로 풀었을 때는 이중 반복문을 사용했었습니다. 지금 와서 보면 효율 고민을 할 게 많은데, 왜 그렇게 풀었을까요. 이번에 풀 때에는 큐를 사용했는데, 성능 차이가 생각보다 컸습니다. 

자바와 이중 반복문

C++와 큐

 

다음은 가장 처음에 생각했던 구조로 다시 작성해 본 결과로, 다른 사람의 풀이법을 참고했습니다. 코드가 간결해졌는데 성능 차이는 별로 없는 것 같습니다.

 

큐로 작성한 풀이

int get_days(int rest, int speed)
{
    if (rest % speed == 0)
        return rest / speed;
    return rest / speed + 1;
}

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

    for (int i = 0; i < progresses.size(); ++i)
    {
        int rest = 100 - progresses[i];
        complete_days.push(get_days(rest, speeds[i]));
    }
    int count = 1;
    int prev = complete_days.front();
    complete_days.pop();
    while (!complete_days.empty())
    {
        int curr = complete_days.front();
        complete_days.pop();

        if (prev >= curr)
            ++count;
        else
        {
            answer.push_back(count);
            count = 1;
            prev = curr;
        }
    }    
    answer.push_back(count);
    return answer;
}

 

반복문 하나로 작성한 풀이

int get_days(int rest, int speed)
{
    if (rest % speed == 0)
        return rest / speed;
    return rest / speed + 1;
}

vector<int> solution(vector<int> progresses, vector<int> speeds)
{
    vector<int> answer;
    for (int i = 0; i < progresses.size(); ++i)
        progresses[i] = (get_days(100 - progresses[i], speeds[i]));
    int prev = 0;
    for (int i = 0; i < progresses.size(); ++i)
    {
        if (answer.empty() || prev < progresses[i])
        {
            answer.push_back(1);            
            prev = progresses[i];
        }
        else
            ++answer.back();
    }
    return answer;
}