[programmers] 택배상자

택배상자 문제

문제 설명

영재가 실어야 하는 택배상자는 1번 부터 n번 상자까지 번호가 증가하는 순서대로 컨테이너 벨트에 일렬로 놓여 영재에게 전달된다. 상자는 1번 부터 순서대로 내릴 수 있으며, 순서가 아닌 택배는 보조 컨테이너 벨트에 실어서 보관할 수 있다. 보조 컨테이너 한쪽 면만 뚫려 있으며, 벨트 안에 있는 상자는 가장 나중에 보관한 상자부터 꺼낼 수 있다. 기사님이 알려준 순서가 적혀있는 orders에 적힌 순서대로 실어야 하며, 보조 컨테이너 벨트를 이용해도 기사님이 원하는 순서대로 상자를 싣지 못한다면 더이상 상자를 싣지 않는다.

문제 풀이 1.

먼저 보조 컨테이너 벨트를 만들기 위해서 가장 나중에 들어간게 먼저 나오는 LIFO를 지원하는 stack자료구조를 이용하여, 순서가 아닌 상자들은 stack에 보관하도록 하였다. 해당 값이 stack의 맨 위에 있다면 해당 값을 제거하고 answer를 1증가 시켜주고, 없다면 1부터 해당 값의 -1까지의 값을 넣어주도록 하였다.

public int solution(int[] orders) {
    int answer = 0;
    Stack<Integer> stack = new Stack<>();

    for (int i = 0; i < orders.length; i++) {
        if (i == 0 && orders[i] == 1) {
            answer++;
            continue;
        }

        if (stack.contains(orders[i])) {
            if (stack.peek() == orders[i]) {
                answer++;
                stack.pop();
            } else {
                break;
            }
        } else {
            answer++;
            for (int j = 1; j <= orders[i] - 1; j++) {
                stack.push(j);
            }
        }

    }

    return answer;
}

풀이 1 실행 결과

정확성이 50%가 나왔는데, for문을 2중으로 사용해서 그런건가 싶어서 아래와 같이 풀이 방식을 바꿔봤다.

문제 풀이 2.

2중 for문을 제거하고 변수로 index를 할당하고, 조건이 맞을 때에만 증가를 시켜줄 수 있도록 코드를 바꿔보았다.
✅ orders[index]가 num(초기 값 1)과 같다면 answer를 1증가시켜주고, num도 1증가시켜줘서 다음 상자를 가져온다. 또한, index도 1증가시켜서, 택배 기사님이 원하는 다음 순서를 비교할 수 있도록 한다.
✅ 만약 stack의 맨 위의 값이 택배 기사님이 원하는 상자와 같다면 answer와 index를 증가시켜 주는데 이때에는 스택에 있는 값을 비교하는 것이기 때문에 num은 증가시키지 않고, 일치하는 stack의 값을 pop()해준다.
✅ 조건문에서 탈출하기 위해서는 아래와 같이 2가지를 체크해 준다.
1. index가 배열의 범위를 벗어난 경우 종료
2. 상자의 숫자가 배열의 개수를 벗어난 경우 종료

public int solution(int[] orders) {
    int answer = 0;
    Stack<Integer> stack = new Stack<>();

    int num = 1;
    int index = 0;
    while (true) {
        if (index >= orders.length) {
            break;
        }

        if (orders[index] == num) {
            answer++;
            num++;
            index++;
            continue;
        } else if (!stack.isEmpty() && stack.peek() == orders[index]) {
            answer++;
            index++;
            stack.pop();
            continue;
        }

        if (num > orders.length) {
            break;
        }

        stack.push(num++);
    }

    return answer;
}

풀이 2 실행결과