Stack 과 Queue

알고리즘 개요

스택, 큐 등의 자료구조를 이용하여, 주어진 문제의 원하는 구조를 만듬

• c++ stl 에서는 기본적으로 stack, queue 자료구조를 제공한다.
• #include, #include
• stack, queue 등은 보통 vector의 메소드를 활용해서 구현할 수 있다.
• stl vector의 메소드를 활용하는 것이 중요

• 순서가 중요할 때는 priority_queue를 활용

예제

2019 kakao 겨울 인턴쉽

크레인 인형뽑기

#include <string>
#include <vector>
#include <stack>

using namespace std;

int solution(vector<vector<int>> board, vector<int> moves) {
    int answer = 0;
    vector<int> temp;
    vector<int> flag;
    for(int i=0;i<moves.size(); i++) {
        int m=moves[i]-1;
        for(int j=0;j<board.size(); j++) {
            if (board[j][m]!=0) {
                if(!temp.empty() && temp.back()==board[j][m]) {
                    temp.pop_back();
                    answer+=2;
                }
                else {
                    temp.push_back(board[j][m]);
                }
                board[j][m]=0;
                break;
            } 
        }
        
    }
    return answer;
}

프로그래머스 기능 개발

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

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;
    int temp=0; 
    int qtemp=0; // qfront 값 저장
    int cnt=0;   // answer cnt
    queue<int> q;
    for(int i=0;i<progresses.size(); i++){
        temp=(100-progresses[i])/speeds[i];
        if(temp*speeds[i]+progresses[i]!=100) temp+=1;
        q.push(temp);
    }
    int qsize=q.size();
     for(int j=0;j<qsize; j++){
        if(j==0) {
            cnt=1;
            qtemp=q.front();
        }
        else if(qtemp<=q.front()){
            qtemp=q.front(); // 9
            answer.push_back(cnt);  //
            cnt=1;
        }
        else if(qtemp>q.front()){
            cnt+=1;
        }
        q.pop();
        if(j==qsize-1){
            answer.push_back(cnt);
        }
    }
    return answer;
}

⇒ 64점 짜리 답

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

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;
    int temp=0; 
    int qtemp=0; // qfront 값 저장
    int cnt=0;   // answer cnt
    queue<int> q;
    for(int i=0;i<progresses.size(); i++){
        temp=(100-progresses[i])/speeds[i];
        if(temp*speeds[i]+progresses[i]!=100) temp+=1;
        q.push(temp);
    }
    int qsize=q.size();
     for(int j=0;j<qsize; j++){
        if(j==0) {
            cnt=1;
            qtemp=q.front();
        }
        else if(qtemp<=q.front()){
            qtemp=q.front(); // 9
            answer.push_back(cnt);  //
            cnt=1;
        }
        else if(qtemp>q.front()){
            cnt+=1;
        }
        q.pop();
        if(j==qsize-1){
            answer.push_back(cnt);
        }
    }
    return answer;
}