[프로그래머스] - 42885_구명보트

문제 소개

• Level 2
• https://school.programmers.co.kr/learn/courses/30/lessons/42885
• 테스트케이스 (추가)
  • [20, 60, 70, 80, 30], 100 / 3

풀이

public int solution(int[] people, int limit) {
    Integer[] peopleArray = Arrays.stream(people).boxed().toArray(Integer[]::new);
    Arrays.sort(peopleArray, Collections.reverseOrder());

    int length = peopleArray.length;
    int last = length-1;
    int[] ch = new int[length];
    int answer = 0;

    for (int i = 0; i < length; i++) {
        int boat = 0;
        if (ch[i] == 1) {
            continue;
        }

        ch[i] = 1;
        boat += peopleArray[i];
        while (last > 0) {
            if (ch[last] == 0) {
                if (boat+peopleArray[last] <= limit) {
                    ch[last --] = 1;
                }
                break;
            }
            last --;
        }
        answer ++;
    }

    return answer;
}

이번 문제에서는 문제 해결은 성공했어도, 효율성에서 다 틀리는 상황이 발생했다.

가장 큰 문제점은 효율성이었고 이를 해결하기 위해 접근한 과정을 기록하려고 한다.

 

효율성의 가장 큰 문제로 생각되는 부분은 바로 while문이었다.

int last = length-1;
while (last > 0) {
    if (ch[last] == 0 && boat+peopleArray[last] <= limit) {
        ch[last] = 1;
        break;
    }

    last --;
}

본래 작성했던 while문은 위와 같았다.

• ch[last] == 0 : 이미 보트를 타고 간 사람인지 체크
• boat + people[last] ≤ llmit : 보트에 타고 있는 사람과 같이 탑승해도 제한을 넘지 않는지 체크

위 코드에서는 두 가지 사실을 간과하고 있었다.

• 정렬을 했음에도 불구하고 가장 몸무게가 적은 사람을 태우지 못한다면 더 크거나 같은 몸무게를 가진 사람도 태우지 못함.
• 가장 작은 몸무게를 가진 사람을 태우고 보냈음에도 다시 마지막부터 탐색을 시작함.

그렇기 때문에 아래와 같은 변경사항을 적용하여 해결 할 수 있었다.

• ch[last] == 0 일 때, 보트에 같이 타고 나간 경우와 못 타고 나가는 경우도 같이 반복문에서 빠져나오도록 수정
• last를 반복문 바깥으로 꺼내 이미 태우고 나간 사람을 배제

그렇게 하여 전반적인 실행 속도가 빨라졌음을 확인할 수 있었다.

변경 전 / 변경 후