[8주차_수요일] 택배 배달과 수거하기

[baexxbin]

• 사이트 : 프로그래머스(PG)
• 문제: 택배 배달과 수거하기
• 번호: 150369
• level2

### 🤔 시간복잡도 고려사항

### 💡 풀이 아이디어

[yeongleej]

🤔 시간복잡도 고려사항

• n ≤ 100,000
• cap ≤ 50

=> 전체 집 방문(100,000) 방문시 배달&수거 과정(최대 cap만큼 50) => O(50 100,000)으로 해결 가능

💡 풀이 아이디어

• 물류창고에서 어떠한 집으로 출발할 때 최대한 멀리 가야함
  • 즉, 마지막 인덱스부터 시작해서 배달과 수거가 모두 끝났다면 다음 인덱스로 넘어감
• 배달하기와 수거하기를 따로 처리해야 함 : 배달을 모두 끝낸 후 수거한다고 생각하기
  • 배달할 때든 수거할 때든 트럭에는 최대 cap개의 상자를 실을 수 있음
  • 실을 수 있는 최대까지 실기

    // 배달하기
    int capD = cap;
    int d = i;
    while(d >= 0) {
      // 실을 수 있는 개수가 초과한다면 초과하지 않을만큼만 실기
       if(capD < deliveries[d]) {
            deliveries[d] -= capD;
                break;
       }
      // 모두 실을 수 있다면 실기
       capD -= deliveries[d];
       deliveries[d] = 0;
       d--;
    }

  • 수거하기도 로직 같음

처음에는 객체를 만들어서 풀었는데 배달상자와 수거상자가 따로 처리되다보니깐 그럴 필요가 없는것 같습니다. 그런데 왜 객체로 하면 17번에서 시간초과가 날까요,,,,, ㅎㅎㅎㅎ

[baexxbin]

🤔 시간복잡도 고려사항

• 1 ≤ cap ≤ 50
• 1 ≤ n ≤ 100,000
• 최대 이동 횟수: 100,00050 (510^6)
• 최대 거리(최대 왕복): 100,0002 (210^5)
• 총 이동 거리 = 최대 이동 횟수*최대 거리 (10^12) → long형 사용
• 시간복잡도: O(N*cap) 10^6

💡 풀이 아이디어

• 가장 멀리있는 집부터 배달
  • 물건이있는 한 무조건 가야하기에 먼 거리부터 해치움
  • 이를 편리하게 계산하기 위해 누적합 사용 (i시점으로부터 배달/수거해야할 총 양)
• 역순으로 배달 시작
  • 현재 지점으로부터 커버가능한 왕복 횟수 구하기
  • 누적합이기 때문에 앞으로 가면서 가능한 왕복 횟수 추가해 나가기
  • 왕복이 필요하면, 현재위치에서 왕복한 거리를 총 거리에 더해줌

  int k = 0;      // 왕복 횟수
  long ans = 0;
  for (int i = n - 1; i >= 0; i--) {
      while (deliveries[i] > cap * k || pickups[i] > cap * k) {   // 현재 위치에서 배달과 수거가 모두 완료되기위한 왕복횟수를 구해야함
          ans += (i+1)* 2L;         // 총거리 갱신: 현재위치에서 왕복 일어남. 해당 내용 더해줌
          k++;                    // 왕복횟수 업데이트
      }
  }
  return ans;

[yeahdy]

🤔 시간복잡도 고려사항

알고리즘: 그리디 시간복잡도: 1 ≤ cap ≤ 50, 1 ≤ n ≤ 100,000 각 집을 한번만 순회하므로 O(N)

💡 풀이 아이디어

• 항상 cap 만큼 수거나 배달을 할건데,선 배달 or 수거 / 후 cap 만큼 충전
• 배달 or 수거 할게 있다면 요청하기
• 배달 or 수거를 다 할때 까지 최대 용량 cap 만큼 더하기
  • 이때 현재 위치까지 왔다 갔다는 뜻으로 현재위치*2 왕복 계산하기
  • 왔다간 이유는 한번 최대용량 만큼 충전하면 이후 남은 집들도 들리면서 배달 or 수거를 하기 때문

잘못생각한 이유: 마지막 집부터 순회를 도는것 까진 아이디어를 생각했는데, 배달 or 수거가 필요한 마지막 집이 어딘지 찾는데 중점을 뒀기 때문에 많은 경우에 대해 하나씩 구현하다가 포기하고 해설 참고......😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭

질문! 그리디 같은 경우는 아이디어를 떠올려서 문제를 구현해야 하는게 많은것 같은데, 이건 문제를 많이 풀어보는게 가장 좋은 방법인가요?

[Jewan1120]

🤔 시간복잡도 고려사항

• 1 ≤ n ≤ 100,000
• 0 ≤ deliveries[i] ≤ 50 , 0 ≤ pickups[i] ≤ 50
• 50 x 100,000 = 5 x 10^7 → O(N)으로 진행

💡 풀이 아이디어

• 가장 멀리 있는 집을 먼저 방문하는 것이 최선 → 그리디
• 배달이나 픽업할 것이 남아있는 집까지 가야하는 횟수만큼 배달, 픽업양을 누적
• 돌아오면서 배달, 픽업하기

for (int i = n - 1; i >= 0; i--) {
    int cnt = 0;
    while (deliveries[i] > delivery || pickups[i] > pickup) {
        cnt++;
        delivery += cap;
        pickup += cap;
    }
    delivery -= deliveries[i];
    pickup -= pickups[i];
    answer += (i + 1) * 2 * cnt;
}

[icegosimperson]

🤔 시간복잡도 고려사항

• 시간복잡도 : N<=100,000 O(N)(완전탐색!!!)

💡 풀이 아이디어

• 구하는 것 : 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리

• 모든 배달과 수거 -> 각 집 방문 -> 전체거리 최소화 -> 멀리있는 집부터 방문해서 돌아오기

      for(int i=n-1; i>=0; i--){ // 가장 먼 집부터 확인
          deliver += deliveries[i];
          pickup += pickups[i];
  
          while(deliver>0 || pickup>0){ // 배달 or 수거할 택배가 있다면
              deliver -= cap; // 방문한 곳은 배달 or 수거
              pickup -= cap;
              answer +=(i+1) * 2; // 물류창고로 다시 돌아오니까 *2
          }
      }
      return answer;

  완전 탐색은 항상 O(N^2)이 아니다....

[KodaHye]

🤔 시간복잡도 고려사항

• 1 <= 배달할 집의 개수 <= 100_000
• 1 <= 재활용 택배 상자의 최대 개수 <= 50
• 배달할 집의 개수와 재활용 택배의 최대 개수를 고려했을 때, 완전 탐색으로 하면 시초남,,, !!

💡 풀이 아이디어

• 맨 마지막집부터 배달 & 수거하면서 최소 거리를 구하는게 중요함!

for(int i = n - 1; i >= 0; i--) {
    d -= deliveries[i];
    p -= pickups[i];

    while(d < 0 || p < 0) {
        d += cap;
        p += cap;

        // 왕복 왔다갔다 하는 거리
        answer += (i + 1) * 2;
    }
}

제겐 그리디, DP가 유독 왤케 어려울까요!! 연습 많이 해야겠습니다!!