2Level / 연습 문제 / 택배상자

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/131704

프로그래머스

풀이 방법

이 문제에서 주의할 점은 시간복잡도로 인한 시간초과 에러가 발생하면 안된다는 점이다.

입력되는 order의 길이가 최대 1,000,000이기 때문에, O(N)의 시간 복잡도를 갖는 메서드 혹은 방법의 사용은 지양해야한다. (shift나 이중 for문, slice 같이 배열 전체를 확인하는 방식)(링크)

나는 이 문제를 stack을 이용해 풀어 봤다.

예외 처리하는데 어려움을 겪었으며, 
각각 컨베이어 벨트에 넣어야할 상자가 order의 순서가 맞을 때, 보조 벨트에 상자가 있고 마지막에 들어온 상자가 지금 넣어야할 상자가 맞을때, 앞의 두 조건에 부합하지 않는 경우 이렇게 크게 3가지로 처리했다.

num은 지금 컨베이어 벨트의 순서를 의미하고 orderIdx는 입력되는 order의 index를 지정하고 stack은 보조 컨베이어 벨트의 역활을 한다.

 

코드

const solution = (order) => {
    let answer = 0;
    let num = 1;
    let orderIdx = 0;
    let stack = [];
    
    while(num <= order.length+1){
        // order의 순서와 들어갈 순서가 같은 경우
        if(num === order[orderIdx]) {
            orderIdx += 1;
            answer += 1;
            num += 1;
            continue;
        }
        // stack에 마지막으로 들어간 물품과 들어갈 순서가 같은 경우
        else if(stack.length !== 0 && order[orderIdx] === stack[stack.length - 1]) {
            stack.pop();
            orderIdx += 1;
            answer += 1;
            continue;
        }
        stack.push(num);
        num += 1;
    }
    return answer;
}