본문 바로가기
알고리즘/알고리즘

[C++] 프로그래머스 : 코딩테스트연습_스택/큐

by 두둠칫 2022. 2. 10.

https://programmers.co.kr/learn/courses/30/parts/12081

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

1. 기능개발

문제 낸 그대로 구현

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;
    
    for(int i=0; i<progresses.size(); i++){
        int releases = 0, days = 0;
        
        while(progresses[i] + speeds[i]*days < 100){
            days++;
        }
        
        for(int j=i; j<progresses.size(); j++){
            progresses[j] += speeds[j]*days;
        }
        
        for(int j=i; j<progresses.size(); j++){
            if(progresses[j] >= 100){
                releases++;
            }
            else{
                i=j-1;
                break;
            }
            if(j==progresses.size()-1)
                i=j;
        }
        answer.push_back(releases);        
    }
    
    
    return answer;
}

 

2. 프린터

pq 디폴트는 max_heap

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

using namespace std;


int solution(vector<int> priorities, int location) {
    int answer = 1;
    
    priority_queue<int> pq;
    queue<pair<int,int>> q;
    
    for(int i=0; i<priorities.size();i++){
        pq.push(priorities[i]);
        q.push({i, priorities[i]});
    }
    
    while(!q.empty()){
        pair<int,int> tmp;
        
        while(q.front().second != pq.top()){
            tmp = q.front();
            q.pop();
            q.push(tmp);
        }
        
        if(q.front().first==location)
            return answer;
        
        q.pop();
        pq.pop();
        answer++;
    }
    
    
    return answer;
}

 

3. 다리를지나는트럭

시간을 구하기 위해 q.push(0)을 했는데 다른 방법은 없을까..

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

using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0;
    
    queue<int> q;
    int w = 0, idx = 0;
    
    while(idx<truck_weights.size() || !q.empty()){
        answer++;
        
        if(!q.empty() && answer>bridge_length){
            w-=q.front();
            q.pop();
        }
        
        if(idx < truck_weights.size()){
            if(w + truck_weights[idx] <= weight){
                q.push(truck_weights[idx]);
                w+=truck_weights[idx];
                idx++;
            }
            else{
                q.push(0);
            }   
        }
    }
    
    return answer;
}

 

4. 주식가격

나중에 스택으로 다시풀기

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

using namespace std;

vector<int> solution(vector<int> prices) {
    vector<int> answer;
    
    int pSize = prices.size();
    
    for(int i=0; i<pSize-1; i++){
        int t = 0;
        for(int j=i+1; j<pSize; j++){
            t++;
            if(prices[i] > prices[j]){
                break;
            }
        }
        answer.push_back(t);
    }
    
    answer.push_back(0);
    
    return answer;
}