Greedy 알고리즘을 이용하여 풀 수 있는 문제였다.
처음에는 1에서 최대 50000까지의 루프 탐색을 25000번 해야하나 했지만
아닌거같아서 중간점을 찾아 중간에서부터 탐색을 진행하여 탐색수를 절반이하로 줄여야 하나 고민했다.
정렬을 하고나니 굳이 중간점을 쓸 필요도 없을것 같아 양 끝에서
i와 j를 각각 최소값 i 최댓값 j 로 정한다음 i+j 가 limit 이 넘는다면 j 만 -해주고 answer 수 1 증가
limit 보다 적다면 i는 + j는 - 해주고 answer수 1증가 시켜서 푸는 방법을 고안하였다.
import java.util.*;
class p구명보트 {
public int solution(int[] people, int limit) {
int answer = 0, j = people.length-1;
Arrays.sort(people);
for(int i = 0 ; i <= j; j--){
if(people[i]+people[j] <= limit) i++;
answer++;
}
return answer;
}
}
'Algorithm > Programers' 카테고리의 다른 글
Lv 2. 귤고르기 (0) | 2024.05.26 |
---|---|
Lv 2. 멀리뛰기 (0) | 2024.05.24 |
Lv 2. 점프와 순간이동 (0) | 2024.05.22 |
Lv 2. 예상대진표 (0) | 2024.05.22 |
Lv 2. N개의 최소공배수 (0) | 2024.04.19 |