프로그래머스 : 택배상자 (Java)
문제
문제 확인하기
풀이
문제의 핵심만 간단하게 요약해보겠다.
- 컨테이너 벨트를 통해 1번부터
n번까지 상자가 오름차순으로 전달되며 컨테이너 벨트의 맨 앞에 있는 상자만 내릴 수 있다.
- 주어진 순서 배열
order에 맞게 k번 상자를 트럭에 실어야 한다.
order 배열의 인덱스가 순서이고 값은 상자의 번호이다.
- 현재 컨테이너 벨트의 맨 앞에있는 상자가 트럭에 실을 순서가 아니면 보조 벨트를 이용한다.
- 보조 벨트는 입구와 출구가 동일한
Stack 형태이다.
- 보조 벨트에 적재하거나, 보조 벨트에서 상자를 꺼내 트럭에 싣는다.
- 보조 벨트를 이용해도
order 순서대로 상자를 싣지 못하면 종료한다.
컨테이너 벨트를 통해 상자가 도착했을 때, 상자가 트럭에 실을 순서와 일치하면 그대로 트럭에 실으면 된다.
도착한 상자가 트럭에 실을 순서와 일치하지 않을 때에는 어떻게 할까?
언제 보조 벨트에 적재해야 하고 언제 보조 벨트에서 상자를 꺼내서 트럭에 실어야 할까?
현재 트럭에 실을 상자의 번호를 order[i]라고 하자. 또 현재 컨테이너 벨트로 도착한 상자의 번호를 k라고 하자.
현재 트럭에 실을 상자의 번호 order[i]가 k보다 크다면, 현재 상자 k를 보조 벨트에 담아두면 된다.
컨테이너 벨트는 오름차순으로 상자를 보내기 때문에 계속해서 상자를 보조 벨트에 담다보면 원하는 상자가 나오기 때문이다.
현재 트럭에 실을 상자의 번호 order[i]가 k보다 작으면, 컨테이너 벨트에서는 원하는 상자를 얻을 수 없다.
보조 벨트를 확인해야 한다.
보조 벨트 맨 앞에 있는 상자가 order[i]와 같으면 보조 벨트에서 상자를 꺼내 트럭에 싣는다.
이때, 한 번만 보조 벨트를 확인하는 것이 아니라 트럭에 실어야 하는 순서의 상자와 보조 벨트 맨 앞에 있는 상자가 일치하지 않을 때까지 수행한다.
이렇게 반복해서 보조 벨트에서 꺼내 싣다가 더 이상 실을 수 없게되면, 다음 순서로 트럭에 실을 상자 order[i]와 현재 컨테이너 벨트의 상자 k를 비교해본다.
order[i]가 k보다 여전히 작다면 더 이상 트럭에 원하는 박스를 실을 수 없다. 따라서 상자 싣기를 종료한다.
아래는 자바로 작성한 풀이 코드이다.
public class Solution {
public int solution(int[] order) {
int answer = 0;
// order 배열의 포인터
int op = 0;
// 컨테이너 벨트에서 현재 확인중인 박스 번호
int currentBox = 1;
// 보조 컨테이너 벨트
Stack<Integer> assistanceBelt = new Stack<>();
while (op < order.length) {
// 트럭에 실릴 박스의 번호가 현재 컨테이너 벨트의 박스 번호보다 크면
if (order[op] > currentBox) {
// 보조 벨트에 현재 박스를 보관한다.
assistanceBelt.push(currentBox);
currentBox++;
}
// 트럭에 실릴 박스의 번호가 현재 컨테이너 벨트의 박스 번호와 같으면
else if (order[op] == currentBox) {
// 트럭에 싣는다.
answer++;
op++;
currentBox++;
}
// 트럭에 실릴 박스의 번호가 현재 컨테이너 벨트의 박스 번호보다 작으면
else {
// 보조 벨트를 확인한다.
while (!assistanceBelt.isEmpty() && order[op] == assistanceBelt.peek()) {
assistanceBelt.pop();
answer++;
op++;
}
// 트럭에 모두 실었으면 종료.
// 또는 여전히 트럭에 실을 박스 번호가 현재 컨테이너 벨트의 박스 번호보다 작으면 종료.
// 보조 벨트에도 원하는 박스가 없고, 컨테이너 벨트는 계속해서 더 큰 번호의 박스가 등장함.
// 따라서 더 이상 박스를 싣지 못함.
if (op >= order.length || order[op] < currentBox) break;
}
}
return answer;
}
}