[프로그래머스][Level2][Java] 구명보트

문제

https://programmers.co.kr/learn/courses/30/lessons/42885

코딩테스트 연습 - 구명보트

 

풀이코드

public int solution(int[] people, int limit) {  //구명보트
    int answer = 0;
    int first = 0;
    List<Integer> list = new ArrayList<>();
    for(int i : people){            // Arraylist에 몸무게 정보 대입
        list.add(i);
    }
    Collections.sort(list);         // 사람들을 몸무게 순으로 오름차순으로 정렬
    while(list.size() != 0){        // 사람들이 없을때까지 반복
        if(list.size() == 1){       // 사람이 1명 남았을 경우
            list.remove(0);   // 보트에 태워보낸다.
            answer += 1;
        }else{
            if(list.get(first) + list.get(list.size()-1) <= limit){ //제일 가벼운 사람 + 무거운 사람이 제한 무게보다 작거나 같을 경우
                list.remove(first);                 // 제일 가벼운 사람과 무거운 사람을 보트에 태워 보낸다.
                list.remove(list.size()-1);
            }else{                                  // 제한 무게보다 무거울 경우
                list.remove(list.size()-1);   // 무거운 사람만 보트에 태워보낸다.
            }
            answer++;
        }
    }
    return answer;
}

처음에는 ArrayList에 구명보트에 태울 사람들을 다 넣은 뒤 오름차순으로 정렬을 해서

제일 가벼운 사람과 제일 무거운 사람을 태웠을때, 그 무게가 제한무게보다 가벼우면 그대로 그 2명을 구명보트에 태워보내고, 만약 그 무게가 제한무게보다 무거우면 무거운 사람만 보트에 태워보내는 알고리즘으로 풀었었다.

이렇게 푼 이유는 구명보트에 2명만 탈 수 있고, 오름차순으로 바꾼 뒤, 제일 가벼운 사람과 제일 무거운 사람을 태웠을 때, 그 무게가 제한무게보다 무거우면 어차피 제일 무거운 사람은 보트에 누구랑도 같이 탈 수 없으므로 혼자태워보내야된다라는 생각이 들었기 때문이다.

근데 이렇게 알고리즘을 짜니

보다시피 문제는 맞았지만 효율성에서 시간초과가 났다. 그래서 다시 생각해보니 굳이 ArrayList를 사용할 필요없이 배열만 이용해도 충분히 풀 수가 있었다. 그래서 다시 풀었던 코드가

public int solution(int[] people, int limit) {          //구명보트
    int answer = 0;
    Arrays.sort(people);                                //가벼운 사람에서 무거운 사람순으로 정렬
    int min = 0;
    int max = people.length - 1;
    for (int m = max; min <= m; m--) {
        if (people[min] + people[m] <= limit){          // 제일 가벼운 사람과 무거운 사람의 무게 합이 제한무게보다 작을 경우
            min++;                                      // 두 사람다 태워보낸다.
        }                                               // 아니면 무거운 사람만 태워보낸다.
        answer++;
    }

    return answer;
}

이것이다. 원리는 똑같지만 훨씬 더 계산들을 줄일 수 있었고 이렇게 풀었더니

보다시피 효율성도 통과하게 되었다.