<Algorithm> 169. 구명보트(Programmers)

1. 구명보트(Programmers)

   사용 알고리즘 :  그리디

• 처음에 풀때는 visited를 이용하여 모든 경우를 확인 했더니 시간초과가 발생했다.

• 곰곰히 생각해보면 visited 필요없이 point를 계속 이동 시켜주면 되는 문제였다. 

• 쉬운문제일수록 효율성에 대해서 생각을 많이 해봐야 겠다.  

문제에 대한 접근&생각

1. 사람들은 각각 무게가 있고 순서없이 존재한다 -> 정렬!
2. 구명보트는 최대 2명 탈 수 있고 제한 무게가 있다 ->  작은 몸무게 + 큰 몸무게를 최선의 선택 -> 그리디  

내 코드 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

import java.util.Arrays; import java.util.List; import java.util.stream.Collectors;   class Solution {     public static void main(String[] args) {         System.out.println(solution(new int[] {50,50,50,50,50},60));     }     public static int solution(int[] people, int limit) {         int answer = 0;         Arrays.sort(people);         /******************************            * 정렬된 사람 무게를 탐색하여 앞 뒤의 포인터를            * 두고 구명보트에 탈 수 있을때까지 포인터를            * 옮겨주는 방식으로 구명보트 수를 구한다.          *******************************/         List<Integer> plist = Arrays.stream(people).boxed().collect(Collectors.toList());         int front = 0;         int end = plist.size()-1;         int boat = plist.size();         while (front <= end) {             while (plist.get(front) + plist.get(end) > limit && end > 0) end--;             if(front>=end)break;             boat--;             front++;             end--;         }         return boat;         /*boolean[] visited = new boolean[people.length];         int boat = people.length;         for(int i = 0; i < people.length; i++) {             int pivot = people[i];             if(visited[i]) continue;             for(int j = people.length-1; j > i; j--) {                 int with = people[j];                 if(pivot+with <= limit && !visited[j]) {                     visited[i] = true;                     visited[j] = true;                     boat--;                     break;                 }             }         }*/     } } Colored by Color Scripter

cs

 

얻은 것

• Array.asList는 같은 자료형만 가능하다. 기본형 < - x -> 참조형