[코딩테스트 연습] stack/queue-기능개발

queue를 사용한 코드

---

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

using namespace std;

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

    for(int i = 0; i < progresses.size(); i++){
        que.push({progresses[i], speeds[i]});
    }

    int day, count = 0;
    while(!que.empty()){
        pair<int, int> qq = que.front();
        day = ceil((double)(100 - qq.first) / qq.second);
        count = 0;

        while(!que.empty()){
            pair<int, int> qqq = que.front();

            if(qqq.first + (day * qqq.second) >= 100) {
                que.pop();
                count++;
            }
            else break;
        }

        answer.push_back(count);
    }

    return answer;
}

풀이:

1. <int, int>형태인 큐에 progresse와 speed를 모두 넣고 난 후, 하나씩 꺼낸다

2-1. 꺼내진 progresse의 완료일을 구하고 큐에 넣어진 progresses를 하나씩 꺼내면서 완료일에 대입한다+count++

2-2. progresse가 완료일에도 기한이 남는다면 2번을 반복한다 +answer.push_back(count)

 

다른 방법을 사용한 코드

---

#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;
}

풀이 :

1. progresse를 하나씩 꺼내보며 완료일을 구한다

2. 자기보다 큰 완료일이 나올 때까지 progresse를 완료시킨다 (++answer.back())

3. 큰 완료일이 나왔다면 answer에 새 공간을 만들고 큰 완료일로 2번을 반복한다  (answer.push_back(1))

 

내 코드와 다른 사람의 코드의 차이점

---

완료일을 구하는 식

day = (99 - progresses[i]) / speeds[i] + 1; // 다른 사람의 코드
day = ceil((double)(100 - qq.first) / qq.second);	// 내 코드

 

기본 바탕이 되는 식은 ( 100 - progresses[i] ) / speeds[i]..인데

여기서 갈라지게 되는 이유는 나눗셈으로 인해 생긴 소수점을 어떻게 처리하느냐..이다

 

내 코드는 캐스터를 사용해서 소수점을 만들고, ceil()로 올림 하는 방법을 썼다

다른 사람의 코드는 소수점이 사라지는걸 이용해서 나누기 전에 -1을 하고 나눈 후에 +1을 해서 자동적으로 올림이 되게 만들었다

 

궁금한 점

---

Q. 그냥 소수점이 있는채로 계산하면 되지 않나

A. 계산하면 100이 나와야 하는데 부동소수점의 영향으로 99.9999...가 나올 수 있기 때문에 주의해야 한다