Lv 2. 택배상자

 

코드흐름

• 영재가 만나게 되는 상자의 번호를 하나씩 for 문으로 루프를 통해 돌린다.
• answer은 여태껏 담아왔던 상자의 갯수이고 이는 order[answer] 은 다음 담아야할 상자를 가리키고 있다.
• 만약 order[answer] 와 i가 일치하면 바로 담아도 되는 상자이므로 answer++해준다.
• 만약 st.peek()과 i 가 같다면 보조 컨테이너에서 다음담을상자를 빼면 되므로 answer++ 해준다.
• 아무런경우에도 해당되지 않으면 stack, 즉 보조 컨테이너에 집어 넣어준다.
• 혹여나 answer, 즉 담아온 상자의 갯수가 order.size() 와 같다면 모두 담은 것이지만 덜담았다면 다시한번 stack에서 확인해주고 만약 더이상 stack 즉 보조 컨테이너에서 꺼내도 다음 담을상자를 찾을수 없다면 while문을 중지해준다.
• answer를 리턴하여 여태 쌓은 상자 갯수를 반환한다.

import java.util.*;

class Solution {
    public int solution(int[] order) {
        int answer = 0;
        Stack<Integer> st = new Stack<>();
        for(int i = 1 ; i <= order.length; i++){ //영재의 마주하는 상자들 순서 i
            while(!st.isEmpty() && st.peek()==order[answer]){
                st.pop();
                answer++;
            }
            if(i == order[answer])
                answer++;
            else
                st.add(i);
        }
        while(answer!=order.length && !st.isEmpty()){
            if(!st.isEmpty() && st.peek()==order[answer]){
                st.pop();
                answer++;
            }
            else break;
        }
        return answer;
    }
}

 

다음은 더욱 간단한 다른사람의 코드이다.

나는 문제의 흐름대로 모두 써내려 갔고 중간의 if 문이 중복되는것을 확인하였다.

이를 해결할 방법을 찾고 있었는데 마침 어떤사람이 문제를 푼 내용을 보고 놀랐다.

모든 번호를 stack에 집어넣고 생각한다는 것이다. 

모든번호를 stack에 집어넣으면 while 문 하나를 안에 집어넣음으로써 문제가 해결 가능해진다.

 

import java.util.*;
class Solution {
    public int solution(int[] order) {
        int idx = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < order.length; i++){
            stack.push(i+1);
            while(!stack.isEmpty()){
                if (stack.peek() == order[idx]){
                    stack.pop();
                    idx++;
                } else break;
            }
        }

        return idx;
    }
}