[프로그래머스][JS / Javascript] 택배 배달과 수거하기

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

프로그래머스

 

접근

접근 방식은 다음과 같다.

왕복이기 때문에 특정 지점까지 가면 그만큼을 돌아와야한다

-> 왕복할 특정 지점의 거리를 줄여나가야함

-> 맨 끝 집 부터 해결해버리자.

-> 끝에서부터 해결...? Stack을 사용하자!

 

예제풀이

본 풀이를 예제에 적용하면 다음과 같다.

 

#예제1

[1 0 3 1 2]

[0 3 0 4 0]

 

5번집까지 다녀온다 (ans+=5)

 

[1 0 2]

[0 3]

 

3번집까지 다녀온다 (ans+=3)

 

[]

[]

 

ans = 8

ans*2 = 16

 

#예제2

[1 0 2 0 1 0 2]

[0 2 0 1 0 2 0]

 

7번집까지 다녀온다

 

[1 0 2 0 1]

[0 2 0 1]

 

5번집까지 다녀온다

 

[1 0 1]

[0 1]

 

3번집까지 다녀온다

 

[]

[]

 

ans = 7+5+3 = 15

ans*2 = 30

 

 

풀이

deliveries 배열의 맨 끝부터 제거(pop)하며 (배달이 완료된 집은 배열에서 사라진다)

box(임시 변수)에 값을 더해준다. (트럭에 박스를 싣는 과정에 비유 가능하다)

이 box가 cap을 넘는다면 초과한 만큼 뱉는다(push). (여기까지만 배달이 가능한 것이다.)

deliveries 배열이 비어버린 경우도 break할 수 있게 처리해주자. (모든 집을 배달 완료 한 경우다)

    while(deliveries.length!==0 || pickups.length!==0) { 
        while(deliveries.length!==0) {
            box += deliveries.pop();
            if(box > cap) {
                deliveries.push(box-cap)
                break;
            };
        }

 

본 과정을 pickups에도 적용한다.

        box = 0;
        while(pickups.length!==0) {
            box += pickups.pop();
            if(box > cap) {
                pickups.push(box-cap)
                break;
            };
        }

 

 

매 루프마다(한번 출발할 때마다)

남은 집의 갯수의 최댓값을 ans에 더해준다 (ans += Math.max(deliveries.length, pickups.length))

        ans += distance;
        distance = Math.max(deliveries.length, pickups.length);

 

ans의 두배를 리턴해주면 끝! (왕복이니까!)

return ans*2;

 

근데 이제... 이렇게 하면 테스트케이스 2번만 틀렸다고 뜨게된다.

본 풀이는 무조건 맨 끝 집을 들리는걸 가정하는데,

주어진 입력의 맨 끝 집에 수거하거나 배달할 박스가 0인 경우에도 이 집을 들리는 걸로 카운트 되기 때문이다.

따라서 입력을 조금 깔끔하게 바꿔주는 작업도 함게 진행하자. (둘다 맨 끝이 0이면 그냥 제거해버린다)

    while(deliveries[n-1]===0 && pickups[n-1]===0) {
        deliveries.pop();
        pickups.pop();
        n--;
    }

 

코드

function solution(cap, n, deliveries, pickups) {
    let ans = 0;
    let box = 0;
    while(deliveries[n-1]===0 && pickups[n-1]===0) {
        deliveries.pop();
        pickups.pop();
        n--;
    }
    let distance = n;
    while(deliveries.length!==0 || pickups.length!==0) { 
        while(deliveries.length!==0) {
            box += deliveries.pop();
            if(box > cap) {
                deliveries.push(box-cap)
                break;
            };
        }
        box = 0;
        while(pickups.length!==0) {
            box += pickups.pop();
            if(box > cap) {
                pickups.push(box-cap)
                break;
            };
        }
        box = 0;
        ans += distance;
        distance = Math.max(deliveries.length, pickups.length);
    }
    
    return ans*2;
}