프로그래머스 (탐욕법) - 구명보트
해당 문제를 처음 풀때에 3가지 방법을 통해 풀어보려고 했습니다. 3가지 방법중 위에 2가지 방법은 효율성에서는 통과하지 못했고 마지막 방식만 통과하였습니다.
처음에는 정렬 없이 각 무게에 대해 다음 무게와의 합이 limit를 넘지않고 최대인 사람의 경우를 찾는 방식으로 진행했습니다.
public int solution3(int[] people, int limit) {
int answer = 0;
int[] peopleWeights = Arrays.copyOf(people, people.length);
for (int i = 0; i < peopleWeights.length; i++) {
int weight = peopleWeights[i];
if (weight > 0) {
for (int j = i + 1; j < peopleWeights.length; j++) {
if (peopleWeights[i] + peopleWeights[j] <= limit) {
int preWeight = weight - peopleWeights[i];
weight = preWeight > peopleWeights[j] ? weight : peopleWeights[i] + peopleWeights[j];
peopleWeights[j] = Math.min(preWeight, peopleWeights[j]);
}
}
if (weight > 0) {
answer++;
}
}
}
return answer++;
}
하지만 효율성을 통과하지 못했고, 이유는 무게에 대해 전체 비교를 진행해야 하는것때문에 그런것으로 보입니다.
두번째 방법은 배열을 리스트에 담은 후 정렬을 하고 난 뒤에 두 무게의 합이 처음으로 제한 조건을 넘지 않을때에 두 무게를 리스트에서 제거 하고 그렇지 않을 경우 처음 무게만 제거하는 식으로 코드를 짰습니다.
int answer = 0;
int[] peopleWeights = Arrays.copyOf(people, people.length);
List<Integer> peopleList = new ArrayList<>();
for (int i = 0; i <peopleWeights.length; i++) {
peopleList.add(peopleWeights[i]);
}
peopleList.sort(Comparator.reverseOrder());
while (!peopleList.isEmpty()) {
int weight = peopleList.get(0);
if (weight + peopleList.get(peopleList.size() - 1) <= limit) {
for (int i = 1; i < peopleList.size(); i++) {
if (weight + peopleList.get(i) <= limit) {
peopleList.remove(i);
break;
}
}
}
answer++;
peopleList.remove(0);
}
return answer;
해당 방법의 문제점은 리스트에서 제거할때의 비용을 계산하지 못한점입니다.
마지막 사용한 방법으로는 정렬을 한 배열에서 처음(최소)과 끝(최대) 배열의 값의 합이 limit를 넘지 않았을 경우 가르키는 인덱스를 증가(최소), 감소(최대)를 하고 아닌경우 감소(최대) 만하는 방식으로 로직을 구현했습니다.
public int solution(int[] people, int limit) {
int answer = 0;
int[] copiedPeople = Arrays.copyOf(people, people.length);
Arrays.sort(copiedPeople);
int minIndex = 0;
int maxIndex = people.length - 1;
while (minIndex <= maxIndex) {
int sum = copiedPeople[minIndex] + copiedPeople[maxIndex];
if (minIndex != maxIndex && sum <= limit) {
minIndex++;
}
maxIndex--;
answer++;
}
return answer;
}
해당 방식은 범위가 지속적으로 감소하는 방향으로 구현했고, 리스트를 제거하거나 값의 치환이 아닌 가르키는 인덱스만 변경하여 비용을 최소화 하였기에 효율성 테스트를 통과했습니다.
'정리 > 알고리즘' 카테고리의 다른 글
탐욕법 - 단속카메라 (0) | 2022.03.03 |
---|---|
탐욕법 - 섬 연결하기 (0) | 2022.03.02 |
탐욕법 - 큰 수 만들기 (0) | 2022.02.23 |
완전탐색 - 카펫 (0) | 2022.02.21 |
완전탐색 - 소수찾기 (0) | 2022.02.19 |
댓글