문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/150369?
2023년 카카오 블라인드에서 나온 따끈따끈한 최신 문제
이 문제를 실제 테스트로 봤으면 어땠을까?
문제 로직은 크게 어렵다고 생각 들진 않았지만 이상하게 푸는데 오래 걸렸다.
문제 핵심 및 풀이
제한사항 부분을 보면 집(n)의 개수가 최대 100,000개이고,
cap은 50까지밖에 되지 않는다.
deliveries와 pickups의 개수 또한 n과 같다.
해당 문제에서는 cap이 50밖에 되지 않는 것은 오히려 반복 횟수를 늘린다.
왜냐하면 50번밖에 담지 못하기 때문에 여러 번 왔다갔다 해야한다..
그래서 완전탐색으로 해당 문제를 풀기에는 비효율적으로 보이고,
실제로 완전 탐색으로 안 풀어도 시간초과가 좀 떠서 최적화를 해야 한다.
최소 이동 거리 구하기
여기서 원하는 것은
각각의 집마다 배달과 수거할 박스 양이 주어지고,
이를 최소한의 움직임으로 모두 처리하는 것이다.
여기서 핵심은 왕복이라는 것이다.
가장 먼 거리에 박스가 하나라도 남아있다면
가장 먼 거리 x2의 비용이 추가로 들어간다.
그래서 무조건 먼 거리부터 처리해야 한다.
먼 거리부터 가능한 cap 개수까지 최대한 채워간다.
이는 배달이나 수거나 똑같다.
먼 거리부터 배달 및 수거 항목을 지워나가면 된다.
위의 예시처럼 cap = 5일 때, 가장 먼 거리부터 지워나간다.
이때, 5번을 바로 지울 수 있지만
그렇게 하지 않고 그냥 6번의 3개에서 2개를 담았다.
어차피 앞에 거부터 없애봤자 뒤에 남아있으면 나중에 다시 가야 한다.
따라서 그냥 무조건 뒤에서부터 차례대로 없애야 한다.
배달과 수거의 관계
여기서 머리 아프게 하는 게, 박스를 놓는 것과 수거하는 것을 동시에 한다.
그래서 배달만을 고려해서 배달할 걸 다 들어도 되는가? 이런 생각이 든다.
결론부터 말하면 배달과 수거는 거의 독립적인 관계로 봐도 상관없다.
어떻게 하는 것이 수거에 유리할까?
당연히 cap을 낭비하지 않기 위해 아무것도 가지고 있지 않은 상태면 된다.
그럼 배달은 어떻게 하는 게 유리할까??
배달할 박스를 모두 들고 가면 된다.
여기서는 최대 cap만큼 들고 갈 수 있으므로,
가장 거리가 먼 곳부터 해서 cap만큼 박스를 든다.
이렇게, 가장 먼 곳까지 배달을 완료했다고 하자.
그럼 이상적인 배달이었다면 이제 손에 든 박스는 더 이상 없을 것이다.
즉, cap = 0인 상태, 수거에 가장 유리한 상태가 되는 것이다.
이제 그냥 돌아가면서 먼 곳부터 수거하면 끝이다.
이렇듯 크게 신경 쓸 필요가 없다.
우리가 중점으로 봐야 할 것은 완료되지 않은 가장 먼 지점을 찾는 것이다.
스택을 활용한 풀이
이 문제에서의 핵심은 항상 가장 끝에 있는 지점,
리스트로 따지면 마지막에 있는 원소이다.
그래서 이를 편리하게 이용할 수 있는 스택으로 접근했다.
deliveries와 pickups의 인덱스는 집의 순서를 나타낸다.
그래서 이 정보-쌍들의 원소를 순차적으로 스택에 쌓았다.
위는 예제로 나온 입력의 정보쌍들을 스택으로 담은 모습을 나타낸 것이다.
자연스럽게 stack의 top에는 가장 뒤에 있는 원소,
즉 가장 멀리 있는 지점의 정보가 오게 된다.
사실 이는 간편하게 설명하기 위한 그림이고,
사실은 위와 같은 스택이 2개가 존재한다.
하나는 배달에 대한 정보가 담겨있는 스택,
나머지 하나는 수거에 대한 정보가 담겨있는 스택이다.
위에서 설명했듯이 어차피 배달이 끝난 뒤에는
박스를 들고 있지 않은 상태이기 때문에 2개의 다른 스택으로 구성해도 된다.
일단 첫 과정에서 해야 할 것은 각 스택에서 0인 값을 없애는 것이다.
수거 스택만을 고려할 때, 가장 멀리 있는 5번째에는 수거할 박스가 없다.
그렇다면 굳이 들릴 필요가 없는 것이다.
이런 이유로 애초에 스택에 담을 때 0인 값은 담지 않도록 한다.
이제 본격적으로 시작할 수 있다.
시작할 때 우리는 들고 있는 박스가 Cap 이상이 되면 안 되기 때문에
배달 스택에는 delCount, 수거 스택에는 pickCount라는 정수형 변수를 둔다.
이제 가장 위에 있는(멀리 있는) 집부터 작업을 시작한다.
두 개의 count 변수 모두 0으로 시작한다.
배달 스택을 cap이 아닌 0부터 시작하는 이유는,
어차피 해당 숫자는 0으로 시작하나, cap으로 시작하나 동일한 효과를 준다.
그래서 수거 스택과 통일성과 편리성을 위해 그냥 0부터 시작한다.
각 스택을 pop 해서, 가장 먼 곳에 있는 박스의 수거 및 배달 작업을 수행한다.
그러면 위와 같이 각각의 Count가 올라갈 것이고,
수거 스택의 pickCount는 Cap = 4와 같기 때문에 더 이상 들지 못한다.
여기서 왕복을 했다는 것을 어떻게 알 수 있을까?
바로 delCount와 pickCount 둘 다 4이면 된다.
왜냐하면 가장 먼 거리까지 가면 cap 만큼의 배달 박스를 소비했을 것이고
돌아올 때는 cap 만큼의 수거 박스를 들고 있을 것이기 때문이다.
이를 알기 위해 위 그림에서 연속적으로 과정을 살펴보면
수거 스택은 멈춰둔 채로 배달 스택만 작업을 계속한다.
여기서 봐야 할 점은 오른쪽 그림에서
delCount의 용량이 하나가 비어서 이를 빼주고 끝낸 것.
이제 둘 다 최대 cap 용량이 됐기 때문에 첫 번째 왕복이 끝난 것이다.
여기서 첫 번째 왕복에서 한 것을 말로 정리해 보면,
"배달 박스 4개(Cap)를 가지고 출발하였고,
3번째 집에 1개, 4번째 집에 1개, 5번째 집에 2개를 줬다.
그리고 가장 먼 지점에서부터 돌아올 때,
4번째 집에서 4개의 박스를 수거해서 돌아왔다 "
이때 왕복을 한번 했기 때문에
가장 먼 거리 x2를 통해 이동 거리에 더해줘야 한다.
이제 같은 원리로 2번째 왕복을 해보면,
이번에는 count들이 cap과 같아지진 않았지만,
스택이 비었으니 작업을 더 이상 할 수 없는 상태가 돼버린다.
여기서도 했던 작업들을 말로 정리해 보면
"박스를 3개 가지고 출발하여, 1번 집에 1개, 3번 집에 2개를 배달했다.
배달을 마치고 돌아올 때는 2번 집에서 3개를 가지고 돌아왔다."
이제 위에서 서술한 로직들을 코드로 구현하면 된다.
실수하기 쉬운 부분
왕복 거리를 계산 시점
나는 이 왕복 거리를 계산하는 시점에서 애를 좀 먹었다.
처음에는 두 count의 값이 cap과 같아지면 그때 계산했었는데,
한쪽 스택이 아예 비어져서 동작을 멈춰버리면
그 스택의 count는 영원히 cap이 되지 못할 수도 있다.
그래서 왕복이 끝났다는 것을 인식하는 조건을 세울 때
스택이 비어있는 것도 같이 체크해야 한다.
코드 구현
C++ 구현 코드
↓
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
// 집의 정보를 담은 구조체
struct Info{
int pos; // 출발지에서의 거리
int amount; // 요구 박스의 양
// 따로 수거와 배달 요구량을 구분해두진 않았음
};
long long solution(int cap, int n, vector<int> deliveries, vector<int> pickups) {
long long answer = 0;
stack<Info> del,pick; // 배달 스택과 수거 스택
// 각 집에서 0을 제외하곤 모두 순차적으로 스택에 담음
for(int i = 0; i < pickups.size(); i++){
if(deliveries[i] != 0) del.push({i+1,deliveries[i]});
if(pickups[i] != 0) pick.push({i+1,pickups[i]});
}
int interval = 0; // 가장 먼 거리를 담기 위해서 만든 변수
int delCount = 0;
int pickCount = 0;
// 두 스택 모두 비어야 끝남
while(!del.empty() || !pick.empty()){
//양쪽다 cap보다 커지거나 스택이 비었거나하면 왕복 끝나는 것으로 간주
if((delCount > cap || del.empty())
&& (pickCount > cap || pick.empty())){
answer += interval * 2; // 왕복 거리 계산
// 초기화
delCount = 0;
pickCount = 0;
interval = 0;
}
// 스택이 비어있지 않을 때와 용량이 남았을 때만 작업
if(delCount <= cap && !del.empty()){
Info info = del.top();
del.pop();
// 배달했던 거리와 수거했던 거리 중 더 먼 거리 선택
interval = max(interval,info.pos);
delCount += info.amount;
// 만약 count가 cap보다 더 커진다면 그 차이만큼만 빼주고 다시 큐에 추가
if(delCount > cap){
del.push({info.pos,delCount-cap});
}
}
// 위에 서술했던 delCount와 원리는 똑같음
if(pickCount <= cap && !pick.empty()){
Info info = pick.top();
pick.pop();
interval = max(interval,info.pos);
pickCount += info.amount;
if(pickCount > cap){
pick.push({info.pos,pickCount-cap});
}
}
}
answer += interval * 2; // 마지막에 양 스택이 동시에 비어서 더해지지 않았을 수도 있음
return answer;
}
두 스택이 동시에 비어서 answer에 값이 더해지지 않을 수 있기 때문에
반복문이 종료되고 마지막에 answer+= interval * 2를 더해주는데,
중복된 값이 더해지지 않을까 우려될 수도 있다.
근데 반복문 안에서 보면 answer에 값을 더해주고 난 뒤 interval을 0으로 설정한다.
그래서 밖에서 answer+= interval * 2를 한다고 해서 중복된 값이 더해지지 않는다.
↑
Java 구현 코드
↓
import java.util.*;
import java.util.stream.*;
class Solution {
// 집의 정보를 담은 클래스
class Info{
int dist; // 출발지에서의 거리
int amount; // 요구 박스량
// 따로 수거와 배달 요구량을 구분해두진 않음
// 생성자
Info(int dist, int amount){
this.dist = dist;
this.amount = amount;
}
}
public long solution(int cap, int n, int[] deliveries, int[] pickups) {
long answer = 0;
Stack<Info> del = new Stack<>(); // 배달 스택
Stack<Info> pick = new Stack<>(); // 수거 스택
// 각 집 정보에서 0을 제외하곤 모두 순차적으로 스택에 담음
for(int i = 0; i < n; i++){
if(deliveries[i] != 0) del.push(new Info(i+1,deliveries[i]));
if(pickups[i] != 0) pick.push(new Info(i+1,pickups[i]));
}
int delCnt = 0; // 배달 count
int pickCnt = 0; // 수거 count
int distance = 0; // 해당 왕복에서 가장 먼 거리를 담는 변수
// 두 스택이 모두 비어야 종료
while(!del.empty() || !pick.empty()){
//양쪽다 cap보다 커지거나 스택이 비었거나하면 왕복 끝나는 것으로 간주
if((del.empty()|| delCnt > cap) && (pickCnt > cap || pick.empty())){
answer += distance*2; // 왕복 거리 계산
// 초기화
delCnt = 0;
pickCnt = 0;
distance = 0;
}
// 스택이 비어있지 않을 때와 용량이 남았을 때만 작업
if((delCnt <= cap) && !del.empty()){
Info delivery = del.pop();
// 배달했던 거리와 수거했던 거리 중 더 먼 거리 선택
distance = Math.max(distance,delivery.dist);
delCnt += delivery.amount;
// 만약 count가 cap보다 더 커진다면 그 차이만큼만 빼주고 다시 큐에 추가
if(delCnt > cap)
del.push(new Info(delivery.dist,delCnt-cap));
}
// 위에 서술했던 delCount와 원리 똑같음
if((pickCnt <= cap && !pick.empty())){
Info pickup = pick.pop();
distance = Math.max(distance,pickup.dist);
pickCnt += pickup.amount;
if(pickCnt > cap)
pick.push(new Info(pickup.dist,pickCnt-cap));
}
}
// 마지막에 양 스택이 동시에 비어서 더해지지 않았을 수도 있음
answer += distance*2;
return answer;
}
}
두 스택이 동시에 비어서 answer에 값이 더해지지 않을 수 있기 때문에
반복문이 종료되고 마지막에 answer+= distance * 2를 더해주는데,
중복된 값이 더해지지 않을까 우려될 수도 있다.
근데 반복문 안에서 보면 answer에 값을 더해주고 난 뒤 distance을 0으로 설정한다.
그래서 밖에서 answer+= distance * 2를 한다고 해서 중복된 값이 더해지지 않는다.
↑
시행착오
해당 문제를 스택으로 접근하는 것은 큰 문제가 없었는데,
스택을 이용하는 방식에 문제가 있었다.
2개의 스택을 사용했지만 배달 스택과 수거 스택으로 분리하지 않았다.
같이 있는 스택과 저장용 스택을 따로 두어서,
저장용 스택은 그냥 옮기는 역할만 했다.
그러다 보니 로직은 다 맞았지만 시간초과로 인해 로직을 새로 만들었어야 했다.
howudong님에게 보내주세요
토스아이디로 안전하게 익명 송금하세요.
toss.me