[문제설명]
영재는 택배상자를 트럭에 싣는 일을 합니다. 영재가 실어야 하는 택배상자는 크기가 모두 같으며 1번 상자부터 n번 상자까지 번호가 증가하는 순서대로 컨테이너 벨트에 일렬로 놓여 영재에게 전달됩니다. 컨테이너 벨트는 한 방향으로만 진행이 가능해서 벨트에 놓인 순서대로(1번 상자부터) 상자를 내릴 수 있습니다. 하지만 컨테이너 벨트에 놓인 순서대로 택배상자를 내려 바로 트럭에 싣게 되면 택배 기사님이 배달하는 순서와 택배상자가 실려 있는 순서가 맞지 않아 배달에 차질이 생깁니다. 따라서 택배 기사님이 미리 알려준 순서에 맞게 영재가 택배상자를 실어야 합니다.
만약 컨테이너 벨트의 맨 앞에 놓인 상자가 현재 트럭에 실어야 하는 순서가 아니라면 그 상자를 트럭에 실을 순서가 될 때까지 잠시 다른 곳에 보관해야 합니다. 하지만 고객의 물건을 함부로 땅에 둘 수 없어 보조 컨테이너 벨트를 추가로 설치하였습니다. 보조 컨테이너 벨트는 앞 뒤로 이동이 가능하지만 입구 외에 다른 면이 막혀 있어서 맨 앞의 상자만 뺄 수 있습니다(즉, 가장 마지막에 보조 컨테이너 벨트에 보관한 상자부터 꺼내게 됩니다). 보조 컨테이너 벨트를 이용해도 기사님이 원하는 순서대로 상자를 싣지 못 한다면, 더 이상 상자를 싣지 않습니다.
예를 들어, 영재가 5개의 상자를 실어야 하며, 택배 기사님이 알려준 순서가 기존의 컨테이너 벨트에 네 번째, 세 번째, 첫 번째, 두 번째, 다섯 번째 놓인 택배상자 순서인 경우, 영재는 우선 첫 번째, 두 번째, 세 번째 상자를 보조 컨테이너 벨트에 보관합니다. 그 후 네 번째 상자를 트럭에 싣고 보조 컨테이너 벨트에서 세 번째 상자 빼서 트럭에싣습니다. 다음으로 첫 번째 상자를 실어야 하지만 보조 컨테이너 벨트에서는 두 번째 상자를, 기존의 컨테이너 벨트에는 다섯 번째 상자를 꺼낼 수 있기 때문에 더이상의 상자는 실을 수 없습니다. 따라서 트럭에는 2개의 상자만 실리게 됩니다.
택배 기사님이 원하는 상자 순서를 나타내는 정수 배열 order가 주어졌을 때, 영재가 몇 개의 상자를 실을 수 있는지 return 하는 solution 함수를 완성하세요.
[제한 조건]
- 1 ≤ order의 길이 ≤ 1,000,000
- order는 1이상 order의 길이 이하의 모든 정수가 한번씩 등장합니다.
- order[i]는 기존의 컨테이너 벨트에 order[i]번째 상자를 i+1번째로 트럭에 실어야 함을 의미합니다.
[나의 풀이]
// 택배상자의 크기는 모두 같다. 1번부터 n번까지 번호가 증가하는 순서대로 벨트에 놓자
// 벨트는 한방향으로만 진행이 가능하여 벨트에 놓인 순서대로 상자를 내릴 수 있다.
// 그러나 벨트에 놓인 순서대로 택배상자를 바로 트럭에 싣게 되면 배달 순서와 맞지 않아 문제발생
// 특정한 순서에 맞게 트럭에 택배상자를 싣자.
// 이때, 순서에 맞지 않는 상자는 보조컨테이너벨트에 놓자. 이 벨트는 스택구조로 형성되어있다.
// 최대 몇개의 상자를 실을 수 있는지 리턴.
// 만약 순서가 4,3,1,2,5라고 예시를 들어보자.
// 이때, 메인 컨테이너 벨트에는 1,2,3,4,5 순서대로 박스가 놓여져 있을 것이다.
// 먼저, 4번 박스부터 실어야 하므로, 보조 컨테이너 벨트에는 1,2,3 박스가 역순으로 저장되어 있게 된다.
// 그 후 3번 박스를 실어야 하므로 보조 컨테이너 벨트에서 3번 박스를 가져와서 싣는다.
// 그 후 1번 박스를 실어야 하는데 보조 컨테이너 벨트의 입구에는 2번 박스가 있고, 메인 컨테이너 벨트에는 5번 박스가 있으므로 박스를 실을 수 없다.
// 따라서, 최대 4,3번 박스를 실을 수 있으므로 2 리턴.
import java.util.*;
class Solution {
public int solution(int[] order) {
int answer = 0;
Stack<Integer> sub_container = new Stack<>(); // 보조 컨테이너 벨트
int container_box = 1; // 현재 메인 컨테이너 벨트에 있는 박스
for (int e : order) {
while(container_box <= order.length) { // 현재 순서에 맞는 택배상자가 올때까지 보조 컨테이너 벨트에 저장
if (container_box == e) { // 메인 컨테이너 벨트에 순서에 맞는 택배상자가 있다면
break; // 반복문 탈출
} else if (!sub_container.isEmpty() && sub_container.peek() == e) { // 보조 컨테이너 벨트에 순서에 맞는 택배상자가 있다면
break; // 반복문 탈출
} else { // 둘 다 없다면, 상자가 있을때까지 보조 컨테이너 벨트에 저장하며 탐색해야 한다.
sub_container.push(container_box); // 보조 컨테이너 벨트에 저장
container_box++; // 1 증가시켜 다음 메인 컨테이너 상자
}
}
// 스택에 다 저장을 했음 && 탐색 시작
if (container_box == e) { // 만약 컨테이너 벨트에서 순서에 맞는 택배상자가 있다면
container_box++; // 메인 컨테이너 벨트에서 하나 꺼내고
answer++; // 정답 증가
} else if (!sub_container.isEmpty() && sub_container.peek() == e) { // 만약 보조 컨테이너 벨트에서 순서에 맞는 택배상자가 있다면
sub_container.pop(); // 보조 컨테이너 벨트에서 하나 꺼내고
answer++; // 정답 증가
} else { // 둘다 없다면 실을 수 없으므로 종료
break;
}
}
return answer;
}
}문제를 읽는데 시간이 꽤 걸렸던 문제이다. (문제설명 가독성이 좀 떨어지는듯..)
그러나 한번 이해하면 구현은 그렇게 어렵지 않은 문제이다.
먼저, 해당 문제에는 두개의 컨테이너 벨트가 존재한다.
첫번째는 택배박스를 트럭에 싣기 전에 1부터 n까지 순서대로 놓여져있는 메인 컨테이너 벨트이고, 두번째는 순서에 맞지 않는 택배박스를 임시로 놓는 서브 컨테이너 벨트이다.
해당 문제에서 우리는 주어진 순서에 해당 하는 택배박스를 메인 컨테이너 벨트 혹은 서브 컨테이너 벨트에 있는지를 확인하고, 이것을 트럭에 싣는 것이다.
만약에 메인 컨테이너 벨트에 없다면, 서브 컨테이너 벨트의 맨 앞의 상자를 확인하고 서브컨테이너에도 없다면 택배상자를 서브 컨테이너 벨트에 보관하고, 메인 컨테이너 벨트에서 다음 택배상자를 확인한다.
즉, 우리가 할일을 정리해보면 다음과 같다.
- 정해진 순서에 따른 택배박스 확인하기
- 메인 컨테이너 벨트에 있는지 확인하기
- 메인 컨테이너 벨트에 있다면 싣기
- 메인 컨테이너 벨트에 없다면 서브컨테이너 확인하기
- 서브 컨테이너 벨트의 맨 앞에 있다면 싣는다.
- 없다면 해당 박스를 서브컨테이너에 넣고 다음 택배상자 확인
- 메인 컨테이너 벨트, 서브 컨테이너 벨트의 맨 앞에 없다면 실을 수 없으므로 종료.
위의 로직을 그대로 구현해주면 끝이다.
문제에서 보면 알수 있듯이 서브 컨테이너 벨트는 Stack 구조이다. 따라서 서브 컨테이너 벨트는 Stack을 이용하여 구현하면 쉽게 구현가능하다.
아래는 채점결과이다.
