https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/submissions/1284860195/
1. 문제 및 접근
다른 항구로 며칠 내 배송할 패키지
i번째는 weight[i]의 무게를 가짐 순서대로 , 최대무게초과 x
주어진 day 안 모든 패키지 보내기 위해 필요한 배의 최소 무게를 반환
주어진 day 안에 보내려면 하루에 몇개씩 묶어보내야 하나 ?
하루에 몇개 씩 보낼 지 정했다면 최소한의 무게를 찾기 위해
순서대로 싣을 수 있네
무게 범위를 탐색
이진 탐색으로 탐색한다고 하면 최악의 경우에 아무 것도 안 보내는 건 너무 말도 안되니까
들어온 배열의 크기를 데이만큼만 나누고 큰거 두개씩 ? 최악의 경우 선정
50,000 일
500kg
2. 첫 생각
최소 조건을 잡는 거에서 0으로 했는데 풀다보니,
정렬하지 않는 배열에서의 순서대로 이진탐색을 하는 것이다.
그래서 left의 기준을 0으로 잡고
좀 더 효율적으로 생각하기 위해서 고민하다
제일 큰 수가 mid보다 크다면, 바로 continue; 하려고 생각했는데
생각해보니 정렬하면 안되는 문제이고, 배열에서 가장 큰 수를 찾아 그 수를 left 값으로 정해야 했다.
right 값 선정에서도 실수가 많았는데 그냥 다 더해서 하면 될 것을 자꾸 효율 추구 어쩌구 하는 생각에
이상하게 생각했다 ㅠㅠ (더 똑똑했음 이게 맞았을거야)
(정렬하면 안되는 걸 정렬한 것과 + 불필요한 과정을 추가한 실수)
3. 풀이
public int shipWithinDays(int[] weights, int days) {
// Arrays.sort(weights);// 정렬을 하지 않고
int capa = weights.length;
int left = 0;
int right = 0; // 최악의 경우를 그냥 첫날에 다 때려넣으면 다음날 아무것도 안 싣어도 되려나
for (int weight : weights) {
left = Math.max(left, weight);
right = right + weight;
}
//
// for (int i = capa - 1; capa - 1 - i < max; i--) {
//
// right = right + weights[i];
// }
while (left < right) {
int mid = (left + right) / 2;
int sum = 0; // 하루에 담을 수 있는 최대 합
int day = 1; // 날짜
//어디에 담아서 뺴쓰는 형식 ?
for (int i = 0; i < capa; i++) {
if (sum + weights[i] > mid) {
day++; // 더 커지면 다음 날로 넘김
sum = 0; // 다시 0으로 초기화
// if (day > days) {
// // day를 더했는데 days를 초과한다면 더 큰 값으로 (왼쪽의 기준을 다시잡고 오른쪽 배열탐색)break;
//// left = mid + 1;
// break;
// }
}
sum = sum + weights[i]; //계속 sum에 더해줘서 다음 수를 담고 day를 유지
}
if (day > days) {
left = mid + 1;
} else {
right = mid;
}
}
// 들어온 mid의 날로 분배하는데, 순서대로 분배하는 규칙 ?
// 넣는 갯수가 중요한 게 아니고 한번에 mid보다 작은 수만큼 넣기
return left;
}
전체 풀이
3-1. 최소, 최대 값 선정
우여곡절이 많았지만,
left의 값 ?
사실 생각해보면
다 배송해야 한다는 기준으로는 그냥 주어진 "배열에서의 가장 무거운 놈"을 최소로 잡으면 된다.
그 최적의 무게를 찾기 않고 젤 큰 무기로 용량을 정하면 끝이니까~
right 값 ?
최대 값은 한번에 그냥 모든 배열의 애들을 다 더해서 최대 무게로 산정하는 것이다.
(여기서 첫 날에 다 넣으면 다음 날 넣는 게 없어서 안되는줄..내가 꼼꼼한거라고 하자 ㅎ)
ex)
{1,2,3,4,5,6,7,8,9,10} 이고, 5일이 주어진다면 ?
right = 10, left = 55
3-2. 이진탐색
right = 10, left = 55
left가 right 값보다 커질 때 까지 반복,
이진탐색의 기준을 중간 값 mid는 현재 중간 값인 32
(하루에 담을 수 있는 값이 32라는 뜻)
sum 은 하루에 그럼 얼마나 담을 수 있는 지 확인하기 위해, 하루마다 더해서 구해갈 것이다.
day는 날짜를 뜻함
3-3. mid과 최적인가 ?
중요한 점은 "배열의 순서대로 싣어야 한다"
그래서 들어온 순서대로 더해주는데, 만약에 sum을 더해가다 담을 수 있는 최적 값(32)보다 커진다면
다른 말로 하루에 담을 수 있는만큼 들어온 순서대로 담다가, 우리가 정해놓은 mid 값을 넘어가게 된다면 다음 날에 싣는다.
아니라면
sum에 현재 순서의 짐을 싣고, 다음 짐을 추가하러 감
mid = 32
1day = 1, 2, 3, 4, 5, 6, 7
2day = 8, 9, 10
3day = 0
4day = 0
5day = 0
현재 day는 2일에 다 끝내기에 2!
3-4. mid 값 조정
현재 day = 2, days =5
day가 들어온 days보다 크다 ?
현재 세어준 날짜가 들어온 날짜안에 수행하지 못한다
5일안에 끝내야 하는데, 6~7일이 걸렸다면 mid의 값이 더 커야 한다.
하루에 담을 수 있는 양(mid)이 부족하니 딱 맞게 못 끝냈단 뜻
최소 값을 mid+1로 해준 다음 그 다시 새로운 mid를 선정 후 다시 반씩 소거
day가 들어온 days보다 작거나 같다 ?
현재 세어준 날짜로는 충분히 가능하지만, 우리는 더 작게 쓸 수 있는 지 확인해야 한다.
현재 day = 2, days =5 이니까,
mid 값을 줄이기 위해 최대 값을 mid로 잡아주고, 새로운 mid를 선정 후다시 반씩 소거
left = 10 그대로, right는 32
새로운 mid = 21로 계속 탐색 반복!
4. 마무리
(2. 첫 생각)처럼 문제를 제대로 파악해서 차근히 접근하지 않고, 기억한대로 배열을 정렬부터한 실수가 컸다..
right 값과 left 값을 선정하는데에 조금이라도 더 효율적을 다가려고 노력하느라 허비했는데
사실 엄청난 차이가 아니긴 하다.
logN의 시간복잡도라면 그 첫 탐색의 배열 크기를 줄일려고 애 쓰는 것 보다 (중요하지 않단 뜻은 아님)
문제를 제대로 파악해서 확실하게 해결하는 것에 애쓰는 비중을 더 높게 잡아야 한다...
그리고 지금 다시 보니 사실
이 for문에서
day가 days보다 커진다면 바로 탈출 후 mid 값을 올려 주는 게 더 효율적으로 보인다..
내 for문에서는 전체 탐색 후 판별하니 불필요한 과정을 조금 더 줄일 수 있어보여
이런 식으로 더 볼 필요도 없으니..
아까 left와 right의 고민보다 훨씬 더 시간 복잡도를 줄일 수 있어서 더 효율적인 검사인 듯 ?
'알고리즘' 카테고리의 다른 글
| 99클럽 코테 스터디 25일차 TIL 순위 (0) | 2024.06.14 |
|---|---|
| 99클럽 코테 스터디 24일차 TIL 가장 먼 노드 (1) | 2024.06.12 |
| 99클럽 코테 스터디 22일차 TIL 입국심사 (0) | 2024.06.10 |
| 99클럽 코테 스터디 21일차 TIL Count Square Submatrices with All Ones (1) | 2024.06.09 |
| 99클럽 코테 스터디 20일차 TIL Partition Array for Maximum Sum (1) | 2024.06.08 |