문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42885
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
풀이
로직
- 처음에는 정렬하고나서 limit의 무게가 될 때까지 가벼운 사람부터 채우는 방식을 선택했었다.
하지만 이 방법으로는 결과가 나오지 않았음.
그래서 핵심 아이디어를 보고 코드를 짰다.
왜 이렇게 해야만 최적의 결과가 되는지는 아직까지 이해가 잘 가지 않는다... ㅠㅠ - 아! 보트 하나에 탈 수 있는 인원은 최대 두명 이라는 조건을 보지 못했다.
이걸 봤으면 그냥 바로 풀었을텐데...! - 느낀 점. 문제를 정확히 봅시다.
- 배열을 정렬하고,
- 가장 가벼운 사람과 가장 무거운 사람을 짝지어 보트를 보낸다.
코드
import java.util.*;
class Solution {
public int solution(int[] people, int limit) {
int answer = 0;
int leftIdx = 0; // 가장 가벼운 사람의 인덱스
int rightIdx = people.length-1; // 가장 무거운 사람의 인덱스
Arrays.sort(people);
while(leftIdx<=rightIdx) {
if(people[leftIdx] + people[rightIdx] <= limit) {
leftIdx++;
rightIdx--;
// 가장 가벼운 사람 + 가장 사람의 무게가 limit 이하이면
// 다음 가벼운 사람, 다음 무거운 사람의 인덱스로 재정의
} else {
rightIdx--;
// limit을 초과하면, 가장 무거운 사람만 보트에 태워보냄.
// 현재 가장 가벼운 사람은 다음 무거운 사람과 짝지어줘야하므로 -- 를 하지 않음.
}
answer++;
}
return answer;
}
}
채점 결과
정확성 테스트
테스트 1 〉 통과 (1.94ms, 73.2MB)
테스트 2 〉 통과 (0.90ms, 74.1MB)
테스트 3 〉 통과 (1.74ms, 78.9MB)
테스트 4 〉 통과 (1.27ms, 74.3MB)
테스트 5 〉 통과 (0.93ms, 85.1MB)
테스트 6 〉 통과 (0.75ms, 76.4MB)
테스트 7 〉 통과 (1.15ms, 79.9MB)
테스트 8 〉 통과 (0.37ms, 72.1MB)
테스트 9 〉 통과 (0.53ms, 77.5MB)
테스트 10 〉 통과 (1.37ms, 81.7MB)
테스트 11 〉 통과 (1.88ms, 66.2MB)
테스트 12 〉 통과 (1.02ms, 79.5MB)
테스트 13 〉 통과 (1.10ms, 74.9MB)
테스트 14 〉 통과 (0.90ms, 73.4MB)
테스트 15 〉 통과 (0.45ms, 72.6MB)
테스트 16 〉 통과 (0.49ms, 76.6MB)
테스트 17 〉 통과 (0.38ms, 70.9MB)
테스트 18 〉 통과 (0.39ms, 86.4MB)
테스트 19 〉 통과 (0.34ms, 77.2MB)
테스트 20 〉 통과 (0.39ms, 76.3MB)
테스트 21 〉 통과 (0.37ms, 77MB)
테스트 22 〉 통과 (0.36ms, 70.8MB)
효율성 테스트
테스트 1 〉 통과 (21.33ms, 56.8MB)
테스트 2 〉 통과 (9.38ms, 55.4MB)
테스트 3 〉 통과 (16.10ms, 70.1MB)
테스트 4 〉 통과 (11.87ms, 56.5MB)
테스트 5 〉 통과 (18.37ms, 56.1MB)
채점 결과
정확성: 81.5
효율성: 18.5
합계: 100.0 / 100.0
좋은 풀이
0xrgb , hestarium , 한슬 , KING_SJ 외 6 명
import java.util.Arrays;
class Solution {
public int solution(int[] people, int limit) {
Arrays.sort(people);
int i = 0, j = people.length - 1;
for (; i < j; --j) {
if (people[i] + people[j] <= limit)
++i;
}
return people.length - i;
}
}
배운 점
- for문을 해석해보자.
- 만약 가장 가벼운 사람 + 가장 무거운 사람의 무게가 limit 이하이면 다음 가벼운 사람으로 넘어감
=> 즉, 보트에무거운 사람 + 가벼운 사람
을 태워서 보냄 - 그렇지 않으면 다음 가벼운 사람으로 넘어가지 않음
=> 즉, 보트에무거운 사람
만 태워서 보냄
- 만약 가장 가벼운 사람 + 가장 무거운 사람의 무게가 limit 이하이면 다음 가벼운 사람으로 넘어감
- 이렇게 되면
i
는무거운 사람 + 가벼운 사람을 태워서 보낸 보트의 수
가 된다. - 전체 사람의 수
- =
**무거운 사람**만 태워보낸 보트의 수
+**무거운 사람 + 가벼운 사람** 을 태워보낸 보트의 수
* 2 이다. - 전체 사람의 수 -
**무거운 사람 + 가벼운 사람** 을 태워보낸 보트의 수
=**무거운 사람**만 태워보낸 보트의 수
+**무거운 사람 + 가벼운 사람** 을 태워보낸 보트의 수
= 보트의 총 개수
- =
- 그러므로 return
people.length - i
가 되는 것
'코딩테스트 - 프로그래머스 > JAVA' 카테고리의 다른 글
[프로그래머스 / 2017 팁스타운 / 자바(JAVA)] 예상 대진표 (0) | 2024.04.04 |
---|---|
[프로그래머스 / 코딩테스트 연습 / 자바(JAVA)] 멀리 뛰기 (1) | 2024.04.03 |
[프로그래머스 / 코딩테스트 연습 / 자바(JAVA)] 점프와 순간이동 (0) | 2024.03.15 |
[프로그래머스 / 코딩테스트 입문 / 자바(JAVA)] 이진수 더하기 (0) | 2024.03.07 |
[프로그래머스 / 코딩테스트 입문 / 자바(JAVA)] 등수 매기기 (0) | 2024.03.06 |