[Programmers] 택배상자 - Javascript

INDEX

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

프로그래머스

 

 

Solution

순서대로 들어오는 택배 상자를 보조 컨테이너(스택)를 활용해서 요구하는 순서에 따라 적재하는 문제입니다.

이 문제에서 요구사항은 너무나 명확합니다. 보조 컨테이너는 마지막에 넣은 택배만 꺼낼 수 있다. 즉, 스택 구조라는 의미입니다. 그래서 이 문제의 정답률이 54%로 Lv2에서 비교적으로 높은 정답률을 기록하지 않았나 싶습니다.

 

우선 필요한 값을 정의합니다.

let answer = 0;
let stack = []; //보조 컨테이너 스택
let orderIdx = 0; //요구 순서 인덱스
let boxIdx = 1; //컨테이너 박스 인덱스

 

컨테이너 박스는 n 번째 박스로 정의됩니다. 따라서 1부터 시작합니다. 그리고 이 인덱스와는 별개로 기사님의 요구 순서가 들어가 있는 order 파라미터에서 사용할 요구 순서 인덱스가 있습니다.

 

이 문제에서 고려해야 할 경우의 수는 세 가지가 있습니다.

1) 컨테이너에서 내려오는 박스의 순서와 기사님의 요구순서가 일치하는 경우

2) 보조 컨테이너(스택)에 쌓여있는 가장 마지막 택배가 기사님의 요구 순서와 일치하는 경우

3) 외에 보조 컨테이너에 쌓아야 하는 경우

코드로 보면 다음과 같습니다.

for(let i=0; i<=order.length; i++){
    if(order[orderIdx] === boxIdx){ //1) 컨테이너에서 내려오는 박스의 순서와 기사님의 요구순서가 일치하는 경우
        answer++;
        orderIdx++;
        boxIdx++;
    }else if(stack.length && stack[stack.length-1] === order[orderIdx]){ //2) 보조 컨테이너(스택)에 쌓여있는 가장 마지막 택배가 기사님의 요구 순서와 일치하는 경우
        answer++;
        orderIdx++;
        stack.pop();
        i--; //한번더
    }else{ //3) 외에 보조 컨테이너에 쌓아야 하는 경우
        stack.push(boxIdx);
        boxIdx++;
    }
}

 

1) 의 경우는 순서가 일치하므로 정답의 개수를 증가시키고, 요구 인덱스와 박스 인덱스를 증가시켜 줍니다.

2)의 경우는 보조 컨테이너의 마지막 택배와 일치하기 때문에 박스 인덱스는 증가시켜주지 않습니다. 대신 요구 인덱스와 answer를 증가시키고 보조 컨테이너에서 빼줍니다. 그리고 한번 더 보조 컨테이너를 검사해줘야 하기 때문에 i를 1 차감시켜 줍니다.

3) 일치하지 않으므로 박스 인덱스는 증가, 보조 컨테이너에 택배를 담습니다.

 

전체코드

function solution(order) {
    let answer = 0;
    let stack = [];
    let orderIdx = 0; //요구 순서 인덱스
    let boxIdx = 1; //컨테이너 박스 인덱스
    for(let i=0; i<=order.length; i++){
        if(order[orderIdx] === boxIdx){
            answer++;
            orderIdx++;
            boxIdx++;
        }else if(stack.length && stack[stack.length-1] === order[orderIdx]){
            answer++;
            orderIdx++;
            stack.pop();
            i--; //한번더
        }else{
            stack.push(boxIdx);
            boxIdx++;
        }
    }
    return answer;
}