Capacity To Ship Packages Within D Days

1011. Capacity To Ship Packages Within D Days Acceptance 51.0%

NOTE

블로그라기 보다는 생각나는 생각나는 대로 두서없이 적는 낙서장이라고 보면 될것 같다.

2019년 4월 4일 15:03~15:30

문제

1. 컨베이어 벨트(배열)에는 D일 동안 차리해야하는 짐들이 있다.
2. 배열의 각 값은 짐의 무게를 표현한다.
3. D일 동안 짐을 나눠 처리할 수 있는 컨베이어벨트 용량의 최소 값을 리턴하라.
4. 짐은 배열의 0부터 순차적으로만 처리할 수 있다.
5. 1 <= D <= weights.length <= 50000
6. 1 <= weights[i] <= 500

생각 흐름 - 무식하게 풀기

1. 문제가 컨베이어 벨트 용량의 최소값을 요구하는 문구에서 살짝 헷갈림
2. 내가 이해하기로는 짐들의 무게를 최대한 D일 동안 최대한 공평하게 나눈 값에서 최대 값이 컨베이어 벨트의 용량인 듯 하다.
3. 첫 번째 예제로 한 번 보자.

   weights = [1,2,3,4,5,6,7,8,9,10], D = 5
   [1,2,3,4,5],[6,7],[8],9,10]
   

4. 모든 짐의 무게를 합치면 55인가.
5. 그럼 하루에 평균적으로 처리해야하는 용량은 11이 된다.
6. 그런데 각 짐의 무게가 다르므로, 여기서 관건은 하루 동안 처리하는 무게의 편차를 최소로 해야할 듯 하다.
7. 원래 표준 편차의 식은 $\sqrt{(X-\mu)^2} = \lvert X-\mu \rvert$ 이므로 이를 구하기 위해 일단, 평균인 11 에서 각 배열의 수를 빼 나가 보자.

   //weights 를 대충 5개로 그룹지음 [1,2,3,4],[5,6],[7,8],[9],[10]
    -> [10,8,5,1],[6,0],[4,-4],[2],[1]
    -> 각 날의 마지막을 다 더하면 0임. 이것이 표준 편자로 최소 값.
    -> 그룹 중 최대 값은 7+8=15.. 그러므로 답은 15
   

8. 그럼 저 그룹을 어떻게 짓는지가 문제…

방법 1 선형적으로 검사 - Greedy

1. 표준편차를 구하고
2. 절대값이 가장 작은 순간까지 인덱스를 움직여서 그룹을 하나씩 찾기
3. 위의 예에서 4번째에서 끊은 이유는 1이 -4보다 절대값이 작기 때문, 그 다음은 0이니깐 당연히 끊고, 그 다음은 7에서 4고 8에서는 -4인데 절대값은 같으므로 허용해서 7과 8을 그룹지음.
4. 근데 흠… 이게 모든 경우에 맞을까??
5. 일단 예제에서는 잘 맞는데,
6. 그룹을 끊을지 말지 판단하는게 남은 일수와 같이 판단해줘야해서 좀 복잡해질 것 같다.
7. 근데 과도한 아웃라이어가 있으면 어쩌지… 그걸 판단할 기준도 있어야할 것 같은데… 아 평균에 뺐을 때 양수이고 평균보다 크면 아웃라이어라고 봐도 되려나.
8. 아 한 개의 그룹이 생성 될 때 마다 나머지 수를 남은 날짜만큼 나눠서 또 평균을 구해야겠다.

2019년 4월 4일 18:40~19:30

1. 아무리 이리저리 조건을 조정해봐도 너무 수치가 민감하게 반응해서 예제조차 한번에 통과하는게 힘드네… 다시 생각해봐야하나;;

2019년 4월 5일 12:20~13:40

1. 너무 답답해서 Discussion 중 하나를 봤는데…. 음 이건 답이 된 다는건 알겠지만 어떻게 저런 코드가 도출됐는지 원리를 모르겠어서 참고할 수준의 답이 아닌 것 같다;;
2. 이해하고 다른 문제에 적용할 수준으로 이해를 해야하는데 내 수준이 아직 그게 안 되네;;
3. 요게 지금은 더 도움된다.
4. 기본적인 발상은 나하고 같은데, 나의 문제점은 한 번의 순회로 다 판단하려고 했다는 것이고, Discussion에서는 하루에 처리할 수 있는 용량을 순차적으로 늘려가면서 최초로 다 선적할 수 있는 컨베이어벨트의 용량을 리턴한 것이다.
5. 그 밑에 댓글로 바이너리 서치가 제안된 내용이 있는데, 3번의 풀이가 그것의 변형인 것이군…