무인도에 갖힌 사람들을 구명보트를 이용해 구출하려고 한다.
구명 보트는 최대 두명씩 한번에 옮길 수 있다.
구명 보트는 가장 적게 사용해야 한다.
구명 보트의 무게 제한은 40kg ~ 240kg 이다.
각 사람의 몸무게는 40kg ~ 240kg 이다.
구명 보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없다.
사람들의 몸무게를 담은 배열 people과 구명 보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트의 개수의 최솟값을 return 하도록 solution 함수를 작성해라
40~240 으로 범위를 지정해주므로, 해당 범위의 값들을 배열을 이용해서 숫자를 세고, 배열에 저장한 값들 중에서 보트를 만들 수 있는 조건이 있으면 해당하는 사람을 빼서 해결하는 방식.
public class Solution {
static public int solution(int[] people, int limit) {
int[] array = new int[241];
for (int i = 0; i < people.length; i++) {
array[people[i]]++;
}
int answer = 0;
int person = people.length;
int nowPoint = 240;
while (person != 0) {
if (array[nowPoint] == 0) {
nowPoint--;
continue;
}
person--;
array[nowPoint]--;
answer++;
for (int i = 240; i >= 40; i--) {
if (array[i] != 0) {
if (i + nowPoint <= limit){
person--;
array[i]--;
break;
}
}
}
}
return answer;
}
}
while(person != 0)
으로 인해서 O(n) 시간 복잡도를 가진다.40~240으로 범위를 지정해주고, 해당 범위의 값들을 배열을 이용해서 숫자를 세고, 배열에 저장한 값들의 개수를 이용해서 최대 횟수를 240*240 의 연산방식을 적용하는 방식.
package programmers;
class Solution {
public int solution(int[] people, int limit) {
int[] array = new int[241];
// 인덱스 값에 넣기
for (int i = 0; i < people.length; i++) {
array[people[i]]++;
}
int answer = 0;
int firstPoint = limit;
int secondPoint = 0;
// 경우 판단하기
while (firstPoint >= 40) {
// 해당 배열의 개수가 0개라면
if (array[firstPoint] == 0) {
firstPoint--;
continue;
}
// limit + 40보다 더 큰 경우라면
if (limit - firstPoint < 40) {
answer += array[firstPoint];
array[firstPoint] = 0;
firstPoint--;
continue;
}
// 두번째 탈 사람을 정하기 위함
// 만약 limit 의 절반 값보다 크다면
if (limit < firstPoint * 2) {
// 두번째 사람은 최대 무게 - 첫번째 탄 사람 무게보다 작아야 한다.
secondPoint = limit - firstPoint;
}
// 만약 limit 의 절반 값보다 작다면
else {
// 해당하는 값 두개씩 묶어서 값에다 더함.
if (array[firstPoint] % 2 == 0) {
answer += array[firstPoint] / 2;
array[firstPoint] = 0;
firstPoint--;
continue;
} else {
answer += array[firstPoint] / 2;
array[firstPoint] = 1;
secondPoint = firstPoint - 1;
}
}
while (secondPoint >= 40) {
if (array[secondPoint] == 0) {
secondPoint--;
continue;
}
// if 문이 필요한가?
if (array[firstPoint] > array[secondPoint]) {
answer += array[secondPoint];
array[firstPoint] -= array[secondPoint];
array[secondPoint] = 0;
secondPoint--;
} else if (array[firstPoint] < array[secondPoint]) {
answer += array[firstPoint];
array[secondPoint] -= array[firstPoint];
array[firstPoint] = 0;
break;
} else {
answer += array[firstPoint];
array[firstPoint] = 0;
array[secondPoint] = 0;
break;
}
}
// secondPoint 을 다 찾아봐도 없다면, 해당하는 배열로 믂어서 더함.
if (array[firstPoint] != 0) {
answer += array[firstPoint];
array[firstPoint] = 0;
}
firstPoint--;
}
return answer;
}
}
상수 while문
으로 인해서, O(1) 시간 복잡도를 가진다.