반응형
문제에서 예시로 주어진 접근 순서를 보고, 가장 멀리 있는 집부터 접근해야 한다는 건 다 캐치했을 것이다.
그런데 cap만큼 감소시키는 것을 불규칙한 vector 값에 바로 접근해서 푸는 건 복잡할 것 같았다.
집의 번수 = 물류창고로부터의 거리이고, 거리에 대한 정보도, 각 거리에 있는 집에 두어야 할/ 수거해야 할 택배 개수에 대한 정보도 동시에 가질 수 있는 방법이 무엇이 있을까 생각하다 보니.. 스택이 생각났다.
내가 접근한 방법은 delieveries와 pickups에서 0이 아닌 값을 갖는 인덱스+1(거리는 1부터니까)를 각 택배 개수만큼 스택에 차례로 넣는것이다. 그럼 스택은 뒤에서부터 빼니까, 우리가 원하는 대로 가장 멀리있는 집의 택배를 이용할 수 있게 된다.
두 스택에서 cap만큼씩 삭제하고, 이때 각각의 스택에서 맨 처음 삭제한 값이 가장 멀리까지 가는 거리가 되므로, top1과 top2에 저장해 둔다. 이때 주의할 점은 스택이 비어있지 않은 경우에만 삭제 해야 한다는 점이다.
한번 순회하고 갔다올 때 top1과 top2 중 더 큰 값에 따라서 갔다와야 한번에 해결할 수 있기 때문에 더 큰 값의 2배 만큼을 answer에 더해주면 된다!
c++ 코드는 아래와 같다.
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
long long solution(int cap, int n, vector<int> deliveries, vector<int> pickups) {
long long answer = 0;
stack<int> st1, st2;
for (int i = 0; i < n; i++) {//스택에 다 넣어준다
for (int j = 0; j < deliveries[i]; j++) {
st1.push(i + 1);
}
for (int k = 0; k < pickups[i]; k++) {
st2.push(i + 1);
}
}
int top1, top2;
while (!st1.empty() || !st2.empty()) {//둘다 스택이 비워지면 그만
top1 = top2 = 0;
for (int i = 0; i < cap; i++) {
if (!st1.empty()) {
if (i == 0) {
top1 = st1.top();
}
st1.pop();
}
if (!st2.empty()) {
if (i == 0) {
top2 = st2.top();
}
st2.pop();
}
}
answer += max(top1, top2) * 2;
}
return answer;
}
반응형
'CO-TE > 프로그래머스' 카테고리의 다른 글
[프로그래머스] c++ LV2 타겟 넘버 / DFS 알고리즘 사용 (0) | 2023.10.17 |
---|---|
[프로그래머스] MYSQL LV2 조건에 맞는 도서와 저자 리스트 출력하기 / 풀이방법 (1) | 2023.10.17 |
[프로그래머스] c++ LV2 요격 시스템 풀이/접근방법 (0) | 2023.10.12 |
[프로그래머스] c++ LV1 대충 만든 자판 (0) | 2023.09.13 |
[프로그래머스] c++ LV1 덧칠하기 (1) | 2023.09.13 |