반응형
오늘의 학습 키워드
이진탐색
알고리즘 문제
- LeetCode Medium 1011. Capacity To Ship Packages Within D Days
- https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/description/
공부한 내용
이진탐색 여러 풀이
오늘의 회고
처음 시도
- 여러 개의 데이터가 있고, 주어진 days 안에 모든 데이터를 탐색해서 범위 최솟값을 찾는 문제였기 때문에 이진 탐색으로 범위를 반으로 줄여가며 최솟값을 찾는 알고리즘을 생각했다.
- 먼저 생각한 건 return 값, 초기 범위 최소값(최소 capa), 초기 범위 최댓값(최대 capa)이다.
- return은 모든 짐(weights)를 정해진 days 안에 모두 나를 수 있는 배 용량의 최솟값이다.
- 이진 탐색 범위 초기 최솟값 min은 weights 중 가장 큰 수로 최소 capa를 의미한다.
- 만약 min이 weights 중 다른 값으로 초기화된다면, weights의 큰 짐을 아예 나를 수 없기 때문에 가장 큰 짐을 최소 capa로 정했다.
- 이진 탐색 범위 초기 최댓값 max는 모든 짐을 한번에 나를 수 있는 capa로 모든 weights 합으로 초기화했다.
- 여기까진 잘 정했는데 이진 탐색 과정에서 문제가 있었다.
- 처음에 문제를 좀 잘 못 이해해서 중간값 mid로 주어진 days와 같은 날짜만큼 모든 짐을 나를 수 있는지에 대해 비교하면서 오류를 범했다. => Case 3번에서 걸림.
- 또한 if 문으로 비교 로직이 많아지면서 로직이 복잡해졌고, 반복문 안에서 continue;를 남발하게 되었다.
해결
- 탐색 범위를 정했다면, 이제 생각해야 할 것은 중간 값으로 탐색 범위에서 어떻게 범위를 좁힐 수 있을지 고민한다.
- 문제에서 탐색 범위 중간값 mid로 해당 capa가 days 안에 모든 짐을 나를 수 있는지 가능 여부를 판단해야 한다.
- 해당 capa (mid)로 모든 짐을 나르는 데 걸리는 최소 날짜를 구해서 days보다 크다면 불가능
- 해당 capa (mid)로 모든 짐을 나르는 데 걸리는 최소 날짜가 days보다 작거나 같다면 가능하다고 판단
- 그 다음으로 가능 여부가 나오면 범위를 어떻게 좁힐 지 결정한다.
- 해당 capa (mid)로 가능하다면, max = mid - 1로 범위를 좁히면, mid 값은 더 작은 capa으로 설정된다.
- 해당 capa (mid)로 불가능하다면, min = mid + 1로 범위를 좁히면, mid 값은 더 큰 capa로 설정된다.
- 이렇게 반복해서 min과 max를 중앙값의 뒤, 앞으로 움직여 중앙값으로 최적 값을 찾아가는 게임이다.
- 즉, max를 움직이는 이유는 가능하지만, 더 최적의 값이 있는지를 찾는 것. min을 움직이는 이유는 불가능하기 때문에 가능한 값을 찾는 것이다.
문제 풀이
내 풀이
class Solution {
//return: 모든 짐을 정해진 days 안에 모두 나를 수 있는 배 용량의 최솟값
int[] weights;
int days;
int max;
int min;
public void findWeight() {
int sum = 0;
int big = weights[0];
for (int w : weights) {
sum += w;
if (w > big) big = w;
}
max = sum;
min = big;
}
public boolean canShip(int capa) {
int sum = 0;
int count = 1;
for (int w : weights) {
sum += w;
if (sum > capa) {
count++;
sum = w;
}
if (count > days) return false;
}
return true;
}
public int shipWithinDays(int[] weights, int days) {
this.weights = weights;
this.days = days;
findWeight();
while (min <= max) {
int mid = (min+max)/2;
if(canShip(mid)) {
max = mid - 1;
} else {
min = mid + 1;
}
}
return min;
}
}
다른 사람 풀이
class Solution {
public int shipWithinDays(int[] weights, int days) {
int left = 0, right = 0;
for(int w : weights)
{
left = Math.max(left, w);
right += w;
}
if (days ==1) return right;
int ans = 0;
// System.out.println(left +" left, right" + right);
while (left < right)
{
int mid = (left+right)/2;
if(canShipPackage(weights, mid, days)){
right = mid;
ans = mid;
} else {
left = mid+1;
}
}
return ans;
}
boolean canShipPackage(int [] weights,int mid,int days)
{
int count = 1;
int sum = 0;
for(int w: weights)
{
if(sum+w > mid)
{
sum = 0;
count++;
}
sum += w;
//System.out.println(count +"," + sum + "," +w);
}
// System.out.println(count +"," + mid);
return count <= days ? true : false;
}
}반응형
'알고리즘' 카테고리의 다른 글
| 99클럽 코테 스터디 20일차 TIL - 그래프 (2) | 2024.06.13 |
|---|---|
| 99클럽 코테 스터디 19일차 TIL - 그래프 (2) | 2024.06.13 |
| 99클럽 코테 스터디 17일차 TIL - 이진탐색 (0) | 2024.06.10 |
| 99클럽 코테 스터디 16일차 TIL - DP (0) | 2024.06.09 |
| 99클럽 코테 스터디 15일차 TIL - DP (1) | 2024.06.08 |
