[프로그래머스] 기능개발 - C++ 스택&큐

 

 

 

내 풀이 - 큐 사용

1. 진도가 100이 되려면 며칠이 걸리는지 days 벡터에 넣어논다.

남은 진도율 : 100 - progresses

작업속도 : speeds

남은 진도율에서 작업속도를 나누면 진도율이 남는 경우가 있다. 이 경우 1을 더해야 한다.

하지만 딱 맞아 떨어지는 경우에는 1을 더할 필요가 없다.

=> 100이 아니라 99에서 빼면 모든 경우에 1을 더해도 된다.

//예시
99-93 = 6, 6/1 + 1 = 7
99-30 = 69, 69/30 +1 = 3

 

2. 첫번째 days 요소를 큐에 넣어놓는다. 그리고 큐의 맨앞과 days를 비교해서 뒤에 오는 days가 더 작으면 큐에 붙인다.

3. 다음 days가 더 크면 큐의 사이즈를 answer에 붙인다. 그리고 큐를 재선언해서 비운다.

4. 반복한 후 큐가 비어있지 않으면 answer에 큐의 사이즈를 붙이고 큐를 비운다.

 

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

	for (int i = 0; i < progresses.size(); i++) {
		days.push_back((99 - progresses[i]) / speeds[i] + 1);
	}
	q.push(days[0]);

	for (int i = 1; i < days.size(); i++) {
		if (q.front() >= days[i]) q.push(days[i]);
		else {
			answer.push_back(q.size());
			q = queue<int>();
			q.push(days[i]);
		}
	}
	if (!q.empty()) answer.push_back(q.size());

	return answer;
}

 

다른 사람 풀이 - 큐 사용 X

 

큐를 사용하지 않고 answer에 바로 개수를 더하는 방법이다.

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);
            max_day = day;
        }
        else
            ++answer.back();
    }

    return answer;
}

 

며칠이 걸리는지를 day에 넣어놓는다.

answer가 비어있거나 먼저 정한 max_day보다 뒤에 오는 day가 더 크면 max_day를 갱신하고, answer에 1을 붙여 큐를 갱신하는 역할을 한다. (여기는 원래 if문을 밑에 따로 두셨던데 어차피 OR문이라 합쳐도 문제없길래 합쳐놨다.)

만약 answer에 값이 있고 앞에서 넣어놓은 max_day가 day보다 크면 answer에 붙여논 수에 1을 더해 같이 배포하는 개수를 늘린다.