ALGORITHM/PROGRAMMERS
[프로그래머스] 구명보트
0298
2020. 11. 23. 21:48
programmers.co.kr/learn/courses/30/lessons/42885
코딩테스트 연습 - 구명보트
무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5
programmers.co.kr
2020-11-23
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
import java.util.Arrays;
class Solution {
public int solution(int[] people, int limit) {
int answer = 0;
Arrays.sort(people);
int idx = 0;
for(int i = people.length-1; i >= idx; i--) {
if(people[i] + people[idx] <= limit) idx++;
answer++;
}
return answer;
}
}
|
cs |
너무 어렵게 생각해서 오래걸렸었다. 제일 무게가 많이 나가는 사람을 먼저 골라라는 힌트를 듣고 다시 풀어봤다. 처음에는 왜 그랬는지 모르겠지만; 제일 무게가 많이 나가는 사람을 고르고 그 앞부터 제일 적게 나가는 순서대로 계산해서 풀었다. 당연히 시간초과가 났었다.
다시 생각해보니, 가장 무게가 많이 나가는 사람+ 가장 적게 나가는 사람<= 구명보트 limit 보다 적게 되면, 가장 무게가 많이 나가는 사람은 무조건 혼자 탈 수 밖에 없다. 이 방식으로 하나의 인덱스는 뒤에서부터, 다른 하나의 인덱스는 앞에서부터 2개씩 뽑아 더해서 limit보다 작은 경우 같은 구명보트를 타게 했다.
예를 들어 문제 예시와 같이 몸무게가 {70, 50, 80, 50} 인 경우 정렬을 하면 {50, 50, 70, 80} 이 되고, 아래와 같이 풀면 된다.
1) count = 1
idx i
| 50 | 50 | 70 | 80 |
2) count = 2
idx i
| 50 | 50 | 70 | 80 |
2) count = 3
idx i
| 50 | 50 | 70 | 80 |