프로그래머스 Lv2 택배 배달과 수거하기 문제

import java.awt.*;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class LV2Express {
    public static void main(String[] args){
        int cap	= 2;//4;
        int n = 7;//5;
        int[] deliveries = {1, 0, 2, 0, 1, 0, 2};//{1, 0, 3, 1, 2};
        int[] pickups	= {0, 2, 0, 1, 0, 2, 0};//{0, 3, 0, 4, 0};

        System.out.print(solution(cap, n, deliveries, pickups));
    }

    public static long solution(int cap, int n, int[] deliveries, int[] pickups) {
        int reqDelCnt = 0;
        int reqPickCnt = 0;
        long dist = 0;
        for(int i = n - 1; i >= 0; i--){
            reqDelCnt += deliveries[i];
            reqPickCnt += pickups[i];

            int goCnt = 0;
            while(reqDelCnt > 0 || reqPickCnt > 0){
                reqDelCnt -= cap;
                reqPickCnt -= cap;
                goCnt++;
            }

            if(goCnt > 0){
                dist += (long)(i + 1) * 2 * goCnt;
            }
        }

        return dist;
    }
}

프로래머스 Lv2 택배 배달과 수거하기 문제

• 해당 문제의 난이도 상승 원인
  • 배달하는 과정에서 발생하는 내림과 수거를하는 과정에서 발생하는 올림을 처리하는 법에 대한 시간복잡도를 가장 낮게가지는 방법 찾기
• 해당 문제를 해결한 방법
  • Greedy + 역방향 스캔 + 누적 잔량 방식을 사용해 해결
• 해당 문제를 해결였던 과정
  • 처음에는 '최단 거리' 라는 말 때문에 BFS와 그와 비교되는 DFS 방식을 생각하였으나 '최단 거리'를 만족하려면 가장 멀리 있는 곳을 처리해야하므로 Greedy를 선택하였고 이를 만족하기 위해 역방향 스캔을 하도록 작업하였다.
  • 그 다음 배달을 하는 작업에 대한 반복문과 수거를 하는 반복문을 한 반복문에 햄버거처럼 담았으나 시간복잡도 오류가 발생함
  • 해결 방법을 잘 모르겠어서 해당 문제에 대한 힌트를 검색하렸고 그 답안으로 '누적 잔량 방식'이란 해결법을 처음 알게 되어 이에 대한 분석 후 내 생각대로 먼저 작성 하여 테스트 실행
  • 그러나 값이 이상하게 나와서 이 때부터 찾아낸 예시코드를 참고하면서 추가적인 이해와 코드를 작성 후 프로그래머스에 주어진 테스트 케이스를 실행 후 코드를 제출하여 정답 처리 됨
• 문제의 핵심
  • '최단 거리'라는 단어가 주어질 때 BFS, DFS 및 Greedy 등 중 어느 알고리즘을 사용할 지 판단
  • Greedy 사용 시 경우에 따라 정방향, 역방향 중 시작을 어디로 할지 판단
  • '누적 잔량 방식' 이란 문제 해결법에 대해 알고 있다면 어떻게 사용할지, 모른다면 이를 학습을 하도록 유도