[프로그래머스/C++] 알고리즘 - 택배 배달과 수거하기

안녕하세요! 테크지니어22입니다.

오늘은 프로그래머스 알고리즘 택배 배달과 수거하기를 풀어보도록 하겠습니다.

 

 

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

프로그래머스

 

[문제 접근]

n은 10만이하이고 시간제한은 딱히 없지만 일반적으로 10초이내이기 때문에 완전탐색은 간당간당해보이지만, 제약 조건들로 거르고 나면 가능하다고 생각했습니다. 그래서 시간제약에 신경쓰지 않았습니다.

최근에 배낭문제를 풀었기 때문에 배낭문제인가? 라고 잠깐 생각했지만, 중복되는 패턴이 잘 관찰되지 않았습니다.

오히려 가장 먼 거리부터 방문해야 최적의 상황이지 않을까라는 생각이 들었습니다. 즉 그리디 알고리즘으로 접근했고 투 포인터를 가미했습니다.

 

 

[풀이 전략]

1. 배달해야 할 가장 먼 집, 수거해야할 가장 먼 집을 저장할 변수 dmi, pmi를 생성 및 초기화합니다.

2. 물류창고로부터 가장 먼 집부터 확인하면서 배달 혹은 수거를 해야할 집을 가리키도록 dmi와 pmi를 옮겨주었습니다.

3.dmi와 pmi 중 가장 먼집을 선택하여 거리를 계산하고 answer에 추가합니다. 

4. 배달과 수거 조건을 각각 따로 생각하여 조건 처리를 해줍니다.

- 먼 집부터 방문하면서 cap이하만큼의 배달 혹은 수거가 가능한지 판단합니다.

5.dmi와 pmi 중 하나가 0이상이면 위 과정을 반복합니다.

[코드]

#include <string>
#include <vector>

using namespace std;

long long solution(int cap, int n, vector<int> deliveries, vector<int> pickups) {
    long long answer = 0;
    
    int dmi = n-1 ;
    int pmi = n-1 ;

    
    while(dmi >= 0 || pmi >= 0 ) {
        
        while(deliveries[dmi] == 0 && dmi >= 0) dmi--;
        while(pickups[pmi] == 0 && pmi >=0 ) pmi--;
        
        answer += (max(dmi,pmi)+1)*2;
        int tmp1 = cap ;
        int tmp2 = cap ;
        
        while(tmp1 > 0  && dmi >= 0) {
            if(tmp1 - deliveries[dmi] >= 0) {
                tmp1 -= deliveries[dmi];
                deliveries[dmi] = 0 ;
            } else {
                deliveries[dmi] -= tmp1 ;
                tmp1 = 0 ;
                break;
            }
            dmi-- ;

        }
        while(tmp2 > 0 && pmi >= 0) {
            if(tmp2 - pickups[pmi] >= 0) {
                 tmp2 -= pickups[pmi];
                pickups[pmi] = 0 ;
            } else {
                pickups[pmi] -= tmp2 ;
                tmp2 = 0 ;
                break;
            }
            pmi-- ;

        }
    }
    return answer;
}

 

[배울 점]

이문제를 푸는데 스트레스를 조금 받고 생각보다 오래걸렸는데, 이유는 문제를 끝까지 제대로 읽지 않아서 그랬습니다.

정확히는 문제의 예제를 1번만 보고 2번을 확인하지 않았습니다. 그래서 배달 혹은 수거의 양이 cap보다 커지면 건너뛰는 실수를 범했습니다.

- 그리디 알고리즘은 문제의 예제를 통해 추가 제약 조건이나 예외사항들을 신경이 더욱 필요합니다.

- 생각한 알고리즘풀이가  맞는데 정답이 틀린다면 문제를 잘 못 이해하거나 문제의 조건을 빼먹었을 확률이 매우 높습니다.