택배상자

문제

풀이

처음 풀이

import java.util.*;
class Solution {
    public int solution(int[] order) {
        int answer = 0;
        // 1 2 3 4 5 -> 이렇게 가지고있고 -> 본 컨테이너
        // 4 3 1 2 5 -> 이렇게 넣어야한다
        // 123 보관 -> 마지막순서부터 꺼내기 가능 (스택) -> 보조 컨테이너
        // 4 싣는다
        // 3 싣는다
        // 끝 -> 각 본 컨테이너와 보조컨테이너에서 넣어야하는 택배박스를 못넣으면 바로끝
        
        // 본 컨테이너
        Stack<Integer> main = new Stack<>();
        for(int i=order.length-1; i>=0; i++) main.push(i);
        // 서브 컨테이너
        Stack<Integer> sub = new Stack<>();
        
        for(int x : order){
            if(main.contains(x)){
                for(int i=0; i<main.size(); i++){
                    if(main.peek()!=x){
                        sub.push(main.pop());
                    }
                    else if(main.peek()==x){
                        main.pop();
                        answer++;
                    }
                }    
            } 
            else if(!main.contains(x)){
                for(int i=0; i<sub.size(); i++){
                    if(sub.peek()==x){
                        sub.pop();
                        answer++;
                    }
                    else if(sub.peek()!=x){
                        break;
                    }
                }
            }
        }
        return answer;
    }
}

맞는지도 모르겠고, 그냥 쭉쭉 풀었는데 메모리초과가 발생. 입력값이 큰데 스택을 2개 구현해서 하나하나씩 집어넣어서 그런거같다.

정답 풀이

import java.util.*;
class Solution {
    public int solution(int[] order) {
        int answer = 0;
        // 1 2 3 4 5 -> 이렇게 가지고있고 -> 본 컨테이너
        // 4 3 1 2 5 -> 이렇게 넣어야한다
        // 123 보관 -> 마지막순서부터 꺼내기 가능 (스택) -> 보조 컨테이너
        // 4 싣는다
        // 3 싣는다
        // 끝 -> 각 본 컨테이너와 보조컨테이너에서 넣어야하는 택배박스를 못넣으면 바로끝
        
        // 본 컨테이너
        int mainC = 1;
        // 서브 컨테이너
        Stack<Integer> subC = new Stack<>();
        
        for(int x : order){
            //서브 컨테이너에 적재 과정
            while(mainC <= order.length){
                if(mainC == x) break;
                else if(!subC.isEmpty() && subC.peek()==x) break;
                else {
                    subC.push(mainC);
                    mainC++;
                }
            }
            
            //탐색
            if(mainC == x){
                answer++;
                mainC++;
            }
            else if(!subC.isEmpty() && subC.peek()==x){
                subC.pop();
                answer++;
            }
            else{ // 두 컨테이너에 모두 없는경우
                break;
            }
        }
        

        return answer;
    }
}

문제이해가 잘 안되는 이상한 문제이다.
아무튼 문제풀이를 해보면 이 문제는 스택이다. 스택을 이용해서 문제를 해결해야한다.
근데 main컨테이너를 1~n까지 담겨있고 1부터 꺼낼수있는데, 이것을 그냥 변수로 구현했다. 그리고 sub컨테이너는 Stack으로 구현했다.

어떤 박스를 놓아야하는지 for each문으로 order를 탐색한다
while문으로 main컨테이너의 숫자가 order.length 보다 낮거나 같은 숫자일때까지 계속 돌려준다.

1. 현재 컨테이너 박스가 order에 놓아야하는 박스랑 같으면 바로 break;
2. 서브 컨테이너의 peek()박스가 order에 놓아야하는 박스랑 같아도 break;
3. 그게 아니라면 전부 main컨테이너++를 해주고 sub컨테이너에 적재한다.

그러고 나서 이제 해당 order의 놓아야하는 box에 대해서 main과 sub컨테이너를 보면서 정답을 구하면된다.
두 컨테이너에 모두 없으면 종료.