[프로그래머스] 스택/큐 - 기능개발

문제

 

풀이 1

#include <string>
#include <vector>
#include <cmath>
using namespace std;

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

	for (int i = 0; i < progresses.size(); i++) {
		days.push_back(ceil((float)(100 - progresses[i]) / speeds[i]));
	}
	int count = 1, before = days[0];

	for (int i = 1; i < days.size(); i++) {
		if (before >= days[i]) {
			count++;
		}
		else {
			answer.push_back(count);
			count = 1;
			before = days[i];
		}
	}
	answer.push_back(count); // 마지막 남은것까지

	return answer;
}

vector만을 사용하여 해결한 풀이

 

풀이 2

#include <string>
#include <vector>
#include <cmath>
#include <queue> 
using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;
    queue<int> q;
    for(int i=0; i<progresses.size(); i++){
        q.push(ceil((float)(100 - progresses[i])/speeds[i]));
    }
    int count = 1, before = q.front(); q.pop();
    
    while(!q.empty()){
        if(before >= q.front()){
            count++;
        }
        else {
            answer.push_back(count);
            count = 1;
            before = q.front();
        }
        q.pop();
    }
    answer.push_back(count);

    return answer;
}

문제의 의도대로 queue를 사용하여 해결한 풀이

queue로 반복문을 사용할 때는 while과 empty()를 이용한다.

 

queue의 멤버 함수 정리

멤버함수	기능
q.size()	큐의 원소의 개수를 리턴한다.
q.empty()	큐가 비어있으면 1을, 비어있지않으면 0을 리턴한다.
q.front()	큐의 첫번째 원소를 참조한다.
q.back()	큐의 마지막 원소를 참조한다.
q.push(val)	큐에 원소를 집어넣는다. 새로운 원소는 큐의 제일 뒤에 추가된다.
q.pop()	큐의 가장 앞 원소를 제거한다 (들어온지 가장 오래된 원소)

 

 

---

다른 사람 풀이

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

day = (99 - progresses[i]) / speeds[i] + 1는 각 progresses에 대한 남은 날이다.

speed가 100이면 progress 1 이상일 경우, day가 0 나와버려서 뒤에 +1을 해주었다.

 

++answer.back() 

answer vector의 맨 뒷 값에 ++ 값을 해주어, count 없이 원하는 결과를 얻을 수 있었다.

 

---

 

https://sarah950716.tistory.com/5

[C++/STL]queue, stack