[4주차_금요일] 42885_구명보트

[yeahdy]

• 사이트 : 프로그래머스(PG)
• 문제: 구명보트
• 번호: 42885
• Level2

[icegosimperson]

🤔 시간복잡도 고려사항 n<= 50,000, O(n logn)

💡 풀이 아이디어 문제 목표 : 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값 최선의 선택 : 가장 무거운 사람을 먼저 태움

• 배열 오름차순 정렬
• left(가장 가벼운 사람), right(가장 무거운 사람)
• 2명 태울 수 있는 경우, 1명만 태울 수 있는 경우 나눠서 계산

    Arrays.sort(people); // 오름차순

        int left = 0; // 가장 가벼운 사람
        for(int right = people.length -1; right>= left; right--){
            if(people[left] + people[right] <= limit){ // 2명 태울 수 있는 경우
                left++;
            }
            // 1명만 태울 수 있는 경우 
            answer++;
        }

[Jewan1120]

🤔 시간복잡도 고려사항

• 1 ≤ 무인도에 갇힌 사람 ≤ 50,000 → 5 * 10^4이므로 O(n logn)으로 진행

💡 풀이 아이디어

• 한 배에 최대한 많이 태울 수 있게 → 그리디
• 몸무게가 작은 사람 + 몸무게가 큰 사람 → 투 포인터
• 오름차 순으로 정렬한 다음, 위 조합으로 두 명을 태울 수 있는지 확인

  while (l <= r) {
  // 작은 사람도 같이 태울 수 있는 지 확인, 아니라면 몸무게 큰 사람 혼자 타고 가기
  if (people[l] + people[r] <= limit) {
      l++;
  }
  r--;
  answer++;
  }

[yeongleej]

🤔 시간복잡도 고려사항

• 사람수 N <= 50,000
• O(N^2)의 완전탐색은 불가
• 선형탐색과 O(NlogN)정도로 풀 수 있는 방법 생각해보기

💡 풀이 아이디어

• 구명보트에는 2명만 탈 수 있음!!
• 1명씩 태울 수 있는 수 - 2명씩 태울 수 있는 수
• 즉, 정렬 후에 가변운 사람과 무거운 사람이 같은 구명보트에 탈 수 있는 방법의 수 찾기

[KodaHye]

🤔 시간복잡도 고려사항

• 1 <= 무인도에 갇힌 사람의 수 <= 50,000 이므로 people배열에 대해 2중 반복문을 사용하면 시간 초과
• 그리디를 통해 O(N)에 해결할 수 있음

💡 풀이 아이디어

• people 배열을 정렬한 뒤 Deque에 담아줌
• while(!q.isEmpty())
  • pollLast를 하며 숫자가 큰 것부터 처리
  • pollLast > limit라면 continue
  • pollLast + peekFirst(큐에 남아 있는 제일 작은 값)과 pollLast + peekLast(큐에 남아 있는 제일 큰 값)을 비교하며 더 크면서 limit 값보다 작거나 같은 값을 선택하여 조건에 해당하면 poll 하기

쉬운 길로만 가지 말기 ㅎㅎ .... 주어진 자원을 최대로 활용해서 문제 풀이하는 습관 들이잣

[baexxbin]

🤔 시간복잡도 고려사항

• 사람 수 : 50000, (10^4)
• O(NlogN)

💡 풀이 아이디어

• 무게순으로 나가야하기에 정렬

• 처음 아이디어: 큰값부터 보면서, limit-cur=target을 구해, target이 있다면 빼주는 방법 생각함

  • 위 방법은 완전히 limit딱 맞을 경우만 생각한 것..
  • target이하 값들까지 보면서 처리해줘야함

    그래서 이분탐색으로 target값 구하고, target 이하 값이랑 같이 탈출할 수 있을때까지 while문으로 확인하는 방법을 풀었으나,, 시간초과 (잘못된 방법)

• 투포인터 문제

  • 작은 값(left), 큰 값(right)를 보면서 같이 나갈 수 있으면 나가기 : left++
  • 같이 못나가면 큰 값만 나가기: right++

구현과정에서 쓸데없이 구현체들이 많이 필요하지고 코드가 더러워지는것 같다면,,, 설계가 잘못되진 않았는지 다시 살펴보자...ㅠㅠ

[yeahdy]

🤔 시간복잡도 고려사항

• 알고리즘: 투포인터 O(NlogN)
• 시간복잡도: 1 <= N <= 50,000
  • 최악의 경우 모든 지점을 다 거치면 O(N)
  • 정렬 필요 O(NlogN)

💡 풀이 아이디어

• 무거운 사람을 먼저 태우고 동승이 가능한지 확인해야 구명보트 개수의 최솟값을 구할 수 있다
• 오름차순으로 정렬했을 때 두 지점을 양 끝에서 시작
• 동승 불가 하다면 무거운 사람만 탈 수 있음 > end--
• 동승이 가능하다면 둘다 탈 수 있음 > start++ end--