떨어지지 않은 주식 가격
#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() 함수를 이용해 풀면 됨
'web > 알고리즘' 카테고리의 다른 글
프로그래머스 알고리즘 고득점 Kit - 완전탐색 (0) | 2024.02.17 |
---|---|
프로그래머스 알고리즘 고득점 Kit - 정렬 (1) | 2024.02.17 |
프로그래머스 알고리즘 고득점 Kit - 힙 (0) | 2024.02.16 |
c++ algorithm 관련 함수들 (1) | 2024.02.11 |
프로그래머스 알고리즘 고득점 Kit - 해시 (0) | 2024.02.11 |