프로그래머스 알고리즘 고득점 Kit - 스택/큐

떨어지지 않은 주식 가격

#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

vector<int> solution(vector<int> prices) {
    vector<int> answer(prices.size());
    stack<pair<int, int>> s; // 가격 안떨어지는 한 계속 push됨
    
    for(int i=0; i<prices.size(); i++) {
        while(!s.empty()) {
            if(s.top().second > prices[i]) {
                // 가격 떨어진 거
                answer[s.top().first] = i - s.top().first;
                s.pop();
            } else break;
        }
        s.push(make_pair(i, prices[i]));
    }
    while(!s.empty()) {
        answer[s.top().first] = (prices.size()-1) - s.top().first;
        s.pop();
    }
    
    return answer;
}

 

- 스택으로 해결 가능하다

- 매번 stack에 push 전에 현재가보다 높은 과거의 기록들을 전부 pop한 후 push 한다, pop 할 때 경과 시간을 answer 벡터 배열에 저장한다

- 자연스레 stack의 top으로 갈 수록 높은 가격대들이 위치함

 

다리를 지나는 트럭

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

using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0; // counter
    int done = 0; // 다리 건넌 truck 수
    int idx = 0; // 다리 건너야 할 truck idx
    int total_weight = 0, total_num = 0; // 다리 위에 있는 truck 수, 무게 합
    
    queue<int> q;
    for(int i=0; i<bridge_length; i++) q.push(0);
    
    while(done < truck_weights.size()) {
        answer++;
        
        // pop 작업
        if(q.front()>0) {
            total_weight -= q.front();
            total_num--;
            done++;
        }
        q.pop();
        
        // push 작업
        if(idx<truck_weights.size() && total_num<=bridge_length && total_weight+truck_weights[idx]<=weight) {
            q.push(truck_weights[idx]);
            total_weight += truck_weights[idx];
            total_num++;
            idx++;
        } else {
            q.push(0);
        }
    }
    return answer;
}

 

- 큐로 해결 가능하다

- 모든 트럭이 다리를 건너기 위해 걸리는 최소 시간, 트럭 최대 대수 / 최대 하중 정해져있음

- 큐의 각 원소가 bridge의 길이 1 블록에 대응된다고 생각, 0보다 큰(트럭 무게값) 값이 들어있는 곳이 트럭의 위치

- 매 시간 간격마다 pop()과 push()가 일어난다 (길이 1만큼 이동)

 

cf) 약간의 효율화를 위해서는 idx가 N-1이면 break 하고 마지막 answer에 bridge_length를 더해도 됨

cf) python이면 from collection import deque 한 뒤 popleft(), append() 함수를 이용해 풀면 됨