0%

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

작성일 Edited on In Disqus:

프로그래머스 - 탐욕법(Greedy)

풀이 과정

이 문제는 O(n^2)로 풀면 시간 초과가 나오는 문제이다.

나는 이 문제를 처음 풀 때, 오름차순으로 정렬한 다음 앞에서부터 차례대로 더해갔는데 이렇게 풀면 무조건 틀린다.
아래 케이스를 보자.

1
[10,20,30,40,50,60,70,80,90], 100

제한 사항에 각 사람의 몸무게는 40kg 이상 240kg으로 되어있지만, 저건 문제를 이해하는데 사용하는 예시이기 때문에 지금은 중요하지 않다.

앞에서부터 차례대로 계산하면

1
2
3
4
5
6
7
10, 20, 30, 40
50
60
70
80
90
-> 6

6이 나오지만, 이 예제는 5가 반환되어야 한다.

1
2
3
4
5
6
10, 90
20, 80
30, 70
40, 60
50
-> 5

이렇게 가장 큰 수와 가장 작은 수를 서로 더해주면 최솟값을 구할 수 있다.

이를 구현하려면, 일단 people 배열을 오름차순으로 정렬한다.
그리고 가장 큰 수와 가장 작은 수를 더한 값이 limit보다 작거나 같으면 start와 count를 증가시킨다.

이런 식으로 start와 end가 만나는 지점까지 반복한다.
start와 end가 만나는 상황은 비교할 대상이 한개(자기자신)밖에는 없을 때이다.
그런 경우에는 무조건 혼자 타야하기 때문에 count를 증가시킨다.

가장 작은 수와 가장 큰 수를 더했을 때 limit보다 크면 가장 큰 수는 혼자 타야하기 때문에 count를 증가시킨다.

이렇게 구현하는 경우 반복문 한 번만 사용하기 때문에 시간복잡도는 O(n)이 된다.

Code (Javascript)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function solution(people, limit) {
  var count = 0;
  var start = 0;
  var end = people.length - 1;

  // 오름차순으로 정렬
  people.sort(function(a, b) {
    return a - b;
  });

  // start와 end가 만나는 지점까지 반복
  // 뒤에서부터 앞으로 반복한다
  for (end; end >= start; end--) {
    // 가장 큰 수와 가장 작은 수를 더한 값이 limit보다 작거나 같으면
    if (people[end] + people[start] <= limit) {
      // start 증가
      start++;
    }
    count++;
  }

  return count;
}

만만하게 보고 풀었다가 정확도 60점 나와서 당황했고, 고쳐서 풀었더니 시간 초과를 보고, 시간복잡도를 줄일 방법이 도저히 생각나지 않아 결국 구글링을 했다.. 눈물.. ㅋ