문제 출처
https://school.programmers.co.kr/learn/courses/30/lessons/42885?language=java(프로그래머스)
학습 키워드
Greedy
시도 방법
(1) 첫시도 : 그때그때 몸무게가 적은 사람들을 보트에 태워보낸다면? (실패)
(2) 두번째시도 : 가장무거운사람과 가장가벼운 사람을 보트에 태워보낸다면? (성공)
내가 작성한 코드
import java.util.Arrays;
class Solution {
public int solution(int[] people, int limit) {
Arrays.sort(people);
int answer = 0;
int start = 0;
int end = people.length -1;
while(start <= end) {
if(people[start] + people[end] <= limit) {
answer += 1 ;
start++;
end--;
} else {
answer += 1 ;
end--;
}
}
return answer ;
}
}
코드설명
시도1) 가장 날씬한 사람부터 태우면? (실패)
예시 케이스 : [ 50 , 50 , 70 , 80 ] , 최대무게 100
이 경우 가장 날씬한 케이스를 50 + 50 으로 한번 태울 수 있다 (최대무게 100)
두번째로 70을 태우고 추가로 80은 못 태우기 때문에 (무게 150) 70만 보낸다.
마지막으로 80을 보낸다.
이 경우는 정상 처리 된다.
예시 케이스 2 : [10 , 30 , 40 , 230 , 240 ] , 최대 240
가장 날씬한 10+30 를 태운다 (240)
두번째로 40 을 태운다 . 그다음 230은 태우면 초과되기 때문이다. (240)
세번째는 230을 태운다.
네번째는 240을 태운다.
총 4개의 보트가 필요하게 된다.
하지만 이 문제에서 최적의 해는 [240] , [10 , 230] , [30,40] 총 3개다.
따라서 가장무거운사람 + 가장가벼운사람 조합으로 구성을 하기로 했다.
시도2) 가장 무거운 사람 + 가장 가벼운 사람
이미 정렬이 되어있기 때문에 start = 0 이 가장 가벼운 사람 , end 가 가장 무거운 사람이다.
[10 , 30 , 40 , 230 , 240] , 최대 240
while 문 시작
start(0) <= end(4) 이고
people[start] (10) + people[end] (240) 은 limit 를 초과하므로 무거운 사람만 태워보낸다. (else 부분)
그리고 태운 사람을 처리하기 위해 end--를 진행했다.
start(0) <= end(3) 이고
people[start] (10) + people[end] (230) 은 limit를 초과하지 않으므로 둘이 같이 태워보낸다. (if부분)
start(1) <= end(2) 이고
people[start] (30) + people[end] (40) 은 limit를 초과하지 않으므로 둘이 같이 태워보낸다. (if부분)
따라서 구명보트에는 다음과 같이 인원이 들어간다.
[240]
[10, 230]
[30, 40]
start(2) <= end(1) 조건을 종료한다.
출력결과
새롭게 알게된 점
가장 최적의 해가 무엇일까? 라는 해를 찾는 여러 방법을 고려해보고 시도해야할 것 같다.
다음에 풀어볼 문제 - ??
#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL
