-
[프로그래머스] 구명보트ALGORITHM/PROGRAMMERS 2020. 11. 23. 21:48
programmers.co.kr/learn/courses/30/lessons/42885
코딩테스트 연습 - 구명보트
무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5
programmers.co.kr
2020-11-23
1234567891011121314import java.util.Arrays;class Solution {public int solution(int[] people, int limit) {int answer = 0;Arrays.sort(people);int idx = 0;for(int i = people.length-1; i >= idx; i--) {if(people[i] + people[idx] <= limit) idx++;answer++;}return answer;}}cs 너무 어렵게 생각해서 오래걸렸었다. 제일 무게가 많이 나가는 사람을 먼저 골라라는 힌트를 듣고 다시 풀어봤다. 처음에는 왜 그랬는지 모르겠지만; 제일 무게가 많이 나가는 사람을 고르고 그 앞부터 제일 적게 나가는 순서대로 계산해서 풀었다. 당연히 시간초과가 났었다.
다시 생각해보니, 가장 무게가 많이 나가는 사람+ 가장 적게 나가는 사람<= 구명보트 limit 보다 적게 되면, 가장 무게가 많이 나가는 사람은 무조건 혼자 탈 수 밖에 없다. 이 방식으로 하나의 인덱스는 뒤에서부터, 다른 하나의 인덱스는 앞에서부터 2개씩 뽑아 더해서 limit보다 작은 경우 같은 구명보트를 타게 했다.
예를 들어 문제 예시와 같이 몸무게가 {70, 50, 80, 50} 인 경우 정렬을 하면 {50, 50, 70, 80} 이 되고, 아래와 같이 풀면 된다.
1) count = 1
idx i
50 50 70 80 2) count = 2
idx i
50 50 70 80 2) count = 3
idx i
50 50 70 80 'ALGORITHM > PROGRAMMERS' 카테고리의 다른 글
[프로그래머스] 줄 서는 방법 (연습문제) (0) 2020.12.12 [프로그래머스] 압축 (2018 KAKAO BLIND RECRUITMENT 3차) (0) 2020.12.08 [프로그래머스] 정수 내림차순으로 배치하기 (0) 2020.11.15 [프로그래머스] 같은 숫자는 싫어 (0) 2020.11.15 [프로그래머스] 스킬트리 (0) 2020.11.11