큐(Queue)

• 큐(Queue)는 대표적인 FIFO(First In First Out) 구조이다. 제일 처음에 넣은 데이터가 처음으로 빠져나온다.
• 기본 함수는 push, pop, empty, front, back, swap 등이 있다.
• 스택과 달리 front 원소와 back 원소에 접근할 수 있다는 특징이 있다.

1. Queue 헤더 파일 선언 및 객체 선언

#include <queue>     // 헤더 파일 선언
queue<데이터 타입> q; // 객체 선언

2. 큐 기본 함수 - push(데이터 추가하기), pop(front 데이터 삭제하기)

q.push(원소);
q.pop()		 // front 데이터가 삭제됨

3. 큐 기본 함수 - front(front 데이터 반환), back(back 데이터 반환)

q.front();
q.back();

4. 큐의 사이즈 반환 - size()

q.size();

5. 큐가 비어있는지 확인 - empty()

q.empty();

6. 두 큐의 내용 바꾸기 - swap(q1, q2)

q.swap(q1, q2);

정답 코드

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

using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;
    queue<int> q;
	
    // 배포까지 남은 일 수를 queue에 담는다.
    for(int i = 0; i < progresses.size(); i++) {
    
    	// 나머지가 0인지 아닌지에 따라 소수점이 있고 없고가 갈림!
        int temp = (100-progresses[i]) % speeds[i];
        
        if(temp == 0)
            q.push((100-progresses[i]) / speeds[i]);
        else
            q.push((100-progresses[i]) / speeds[i] + 1);
    }
	
    // 큐가 비어 있을 때까지 반복 -> pop()하면 삭제되니까 언젠가 멈추겠지!
    while(!q.empty()) {
    	
        int cnt = 0;
        int cur = q.front(); // 가장 처음 데이터를 cur에 저장하고
        q.pop(); 			 // pop()으로 삭제하기
		
        // 기존의 first 값 cur이 다음 순서의 first 값보다 크면 
        // 비어있는지에 대한 예외 처리 필수
        while(cur >= q.front() && !q.empty()) {
            q.pop();
            cnt++;
        }
        
		cnt++; // 처음 값 뺐으니까 1 증가
        answer.push_back(cnt);
    }
    return answer;
}

분석

• 배포까지 남은 일 수를 구하는 과정이 나와 달랐다. temp를 int형으로 선언하고, 나머지가 0이면 정수니까 그대로 queue에 담는다. 나머지가 0이 아니면 소수점이 존재한다는 것이므로 1을 증가시켜 담는다.
• cnt 초기화는 while문 처음에 고정해두고, cur로 저장 + pop으로 제거 + cnt 1 증가 조합으로 큐의 기본 성질을 최대한 이용한 풀이다. 큐 자료구조를 공부하기에 좋을 문제였던 것 같다.

패착 요인 (내 코드)

#include <string>
#include <vector>
#include <iostream>
#include <stack>
#include <algorithm>

using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;
    vector<int> days;
    stack<int> release;
    
    // 배포까지 남은 일수를 각각 days 벡터에 저장
    for (int i = 0; i < progresses.size(); i++) {
        
        float v2 = (100 - progresses[i]) / speeds[i];
        
        // 소수점 이후 값이 존재하면 올림 처리
        if (v2 > (int)v2) {
            
                int v = (int)v2 + 1;
                days.push_back(v);
            
            } else if (v2 == (int)v2) {
            
                days.push_back(v2);                
            }
        }
    
    int j = 0;
    
    while (1) {
        
        int sum = 0, count = 0;
        
        // j번째 원소만큼 뺀 값을 days 벡터에 각각 저장
        for (int i = 0; i < days.size(); i++) {
            
            days[i] -= days[j];
        }
        
        int val = 0;
        
        // days 벡터 원소가 0보다 작으면 count 1 증가 그렇지 않으면 break
        for (int i = 0; i < days.size(); i++) {
            if (days[i] < 0) {
                count++;
                val = i + 1;
            } else if (days[i] == 0) {
                count++;
            } else break;
        }
        count -= val;
        answer.push_back(count);
        
        // answer 원소 합 = sum
        sum += count;
        
        // sum이 전체 프로세스 수와 같으면 종료
        if (sum == progresses.size()) {
            break;
        }
        
        // while 문의 반복마다 j의 인덱스 증가
        j++;
    }
    
    return answer;
}

• 가능한 스택/큐 문제니까 스택으로 풀어보려고 했다.
• days 벡터를 만드는 과정까지는 다른 정답자들과 동일했지만, 이외 내용이 너무 복잡해졌다.
• 시간이 너무 오버되서 컴파일은 되었지만 결과를 낼 수는 없었다.
• 정답 코드 분석한거 확실하게 인지/숙지하자.