[Programmers] 기능개발

https://programmers.co.kr/learn/courses/30/lessons/42586?language=python3

코딩테스트 연습 - 기능개발 | 프로그래머스

 

큐를 이용해 푸는 문제

 

C++로도 풀어보고

 

python3을 사용해서도 풀어봤다.

 

- 풀이 방법

 

1. 입력으로 들어오는 progresses, speeds에 대해 각각 큐를 만들고 큐에다가 값을 넣었다.

 

2. 한번씩 speeds를 다 더해준다.

 

3. 100이 넘는 값이 있을 경우 큐의 pop 원리를 이용해서 값을 빼준다.

(없을 경우 반복문 종료)

 

4. 답을 출력한다.

 

- C++ 풀이

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

using namespace std;

queue<int> p_q, s_q;

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;
    
    for (int i = 0; i < progresses.size(); i++) {
		p_q.push(progresses[i]);
		s_q.push(speeds[i]);
	}

	while (1) {
		if (p_q.empty()) break;

		queue<int> temp, temp_speed;

		int length = p_q.size();
		for (int i = 0; i < length; i++) {
			int p_front = p_q.front();
			int s_front = s_q.front();
			p_q.pop(), s_q.pop();
			temp.push(p_front + s_front);
			temp_speed.push(s_front);
		}	

		int cnt = 0;
		while (!temp.empty()) {
			int temp_front = temp.front();

			if (temp_front >= 100) {
				cnt += 1;
				temp.pop();
				temp_speed.pop();
			}
			else break;
		}

		int len = temp.size();
		for (int i = 0; i < len; i++) {
			p_q.push(temp.front());
			temp.pop();
			s_q.push(temp_speed.front());
			temp_speed.pop();
		}
		if(cnt != 0) answer.push_back(cnt);
	}
    
    return answer;
}

 

 

-python 풀이

from collections import deque

def solution(progresses, speeds):
    answer = []
    
    length = len(progresses)

    dq_progresses = deque()
    dq_speeds = deque()

    for i in range(0, length):
      dq_progresses.append(progresses[i])
      dq_speeds.append(speeds[i])

    while(True):
        if(len(dq_progresses) == 0):
            break

        sum_len = len(dq_progresses)

        for i in range(0, sum_len):
            dq_progresses[i] += dq_speeds[i]

        cnt = 0

        while(True):
            dq_len = len(dq_progresses)

            if dq_len == 0:
                break

            if dq_progresses[0] >= 100:
                cnt += 1
                dq_progresses.popleft()
                dq_speeds.popleft()
            else:
                break

        if cnt != 0:
            answer.append(cnt)
        
    return answer