-
[프로그래머스] 구명보트 - Java알고리즘 문제 풀이 2024. 4. 29. 16:40
문제 - 구명 보트
https://school.programmers.co.kr/learn/courses/30/lessons/42885
문제 설명
제한 사항
입출력 예
people limit return [70, 50, 80, 50] 100 3 [70, 80, 50] 100 3
접근 방법
- 문제에 구명보트를 최대한 적게 사용하여 모든 사람을 구출한다 라고 봤을때 최적의 값을 구하는 알고리즘 중에서 탐욕법(그리드)을 생각 할 수 있다
- 한 구명 보트 당 최대 2명 사용할 수 있다고 한다
- 자료구조는 특별한거 없이 배열로 사용 하면 될 것 같다
코드 작성
import java.util.*; class Solution { public int solution(int[] people, int limit) { int answer = 0; int min = 0; Arrays.sort(people); for(int max = people.length -1; min <= max; max--){ if(people[min] + people[max]<= limit){ min++; } answer++; } return answer; } }
- 모든 사람을 구출 해야 하니 반복문을 최대 사람수 부터해서 줄여 나가면 될 것 같다
문제 풀고 느낀점
- 이 문제는 탐욕법 알고리즘에 대해서 알고 있어야 풀 수 있는 문제 인 것 같다
'알고리즘 문제 풀이' 카테고리의 다른 글
[백준] 1991 트리 순회 - Java (1) 2024.05.01 [백준] 11279 최대 힙 - Java (0) 2024.04.30 [백준] 5430 AC - Java (0) 2024.04.28 [백준] 1158 요세푸스 문제 - Java (0) 2024.04.27 [백준] 10845 큐 -Java (1) 2024.04.25