[131704] 택배상자

✔ 택배상자

[프로그래머스 131704]

문제 분석하기

스택을 이용해 1부터 자연수를 증가시키면서 입력으로 주어진 상자 순서와 비교하여 증가시킨 자연수를 스택에 추가하거나 빼도록 함

손으로 풀어보기

1. 1부터 자연수를 증가시키면서 입력으로 주어진 상자 순서와 비교하여 증가시킨 자연수를 스택에 추가하거나 빼는 방식 이용
2. 현재 상자 순서 값 >= 자연수일 경우
   • 현재 상자 순서 값이 자연수보다 크거나 같을 때까지 자연수를 1씩 증가시키며 스택에 push한 후, 마지막 1회만 pop
3. 현재 상자 순서 값 < 자연수일 경우
   • pop으로 스택에 있는 값을 꺼낸 후, 꺼낸 값이 현재 상자 순서 값이 아니라면 상자 순서를 표현할 수 없게 됨

슈도코드 작성하기

order(택배 기사님이 원하는 상자 순서)
answer(영재가 실을 수 있는 상자의 개수)
stack(상자를 담을 스택)
num(오름차순 자연수) = 1
for(i -> order의 크기만큼 반복) {
    box(현재 상자의 값)
    if(box가 num보다 크거나 같다면) {
        while(box와 num이 같아질 때까지) {
            스택에 num++ 저장
        }
        stack의 가장 위의 수가 box와 같으므로 pop
        answer 증가
    }
    else(box가 num보다 작다면) {
        top(스택의 가장 위의 수)
        if(top이 box보다 크다면)
            더이상 상자를 실을 수 없으므로 break;
        else
            answer 증가
    }
}
answer 반환

코드 구현하기

/**
 * 131704) 택배상자
 */
public class L081_131704 {
    // order(택배 기사님이 원하는 상자 순서)
    public int solution(int[] order) {
        // answer(영재가 실을 수 있는 상자의 개수)
        int answer = 0;
        // stack(상자를 담을 스택)
        Stack<Integer> stack = new Stack<>();
        // num(오름차순 자연수)
        int num = 1;
        for (int i = 0; i < order.length; i++) {
            // box(현재 상자의 값)
            int box = order[i];
            // box가 num보다 크거나 같다면
            if (box >= num) {
                // box와 num이 같아질 때까지
                while (box >= num) {
                    // 스택에 num++ 저장
                    stack.push(num++);
                }
                // stack의 가장 위의 수가 box와 같으므로 pop
                stack.pop();
                // answer 증가
                answer++;
            }
            // box가 num보다 작다면
            else {
                // top(스택의 가장 위의 수)
                int top = stack.pop();
                // top이 box보다 크다면
                if (top > box)
                    // 더이상 상자를 실을 수 없으므로 break;
                    break;
                else
                    // answer 증가
                    answer++;
            }
        }
        // answer 반환
        return answer;
    }

    // 테스트 케이스
    public static void main(String[] args) {
        L081_131704 solution = new L081_131704();

        int[] order = { 4, 3, 1, 2, 5 };

        int result = solution.solution(order);

        System.out.println(result);
    }
}