https://school.programmers.co.kr/learn/courses/30/lessons/42885#qna
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
코드
import java.util.*;
class Solution {
public int solution(int[] people, int limit) {
/*
people을 내림차순 정리한다 -> quick sort 이므로 O(nlogn)
최댓값부터 limit 만족하는 두가지 골라본다.
$ 효율성 테스트가 통과될까 궁금하다.
*/
/*
첫 풀이 : 테스트 실패, 효율성 시간초과, 시간 25분
*/
int answer = 0;
Integer[] arr = Arrays.stream(people).boxed().toArray(Integer[]::new);
Arrays.sort(arr, Collections.reverseOrder());
ArrayList<Integer> list = new ArrayList<>();
for(int item : arr){
list.add(item);
}
label: while(list.size()>0){
for(int i=0; i<list.size(); i++){
for(int j=i+1; j<list.size(); j++){
if(list.get(i)+list.get(j)<=limit){
answer++;
list.remove(i);
list.remove(j);
continue label;
}
}
answer++;
list.remove(i);
continue label;
}
}
return answer;
}
}
다른 분들의 풀이
우선 나의 논리가 틀렸다기 보다는 최적이 아니었다.
나는 가장 큰 값을 먼저 찾고, 더했을 때 limit 을 만족하는 다음 큰 값을 찾아 더해서 구명보트에 실어보내는 방식을 생각했다.
왜냐하면 가능하면 작은 값이 남아있을 수록 유리할 것으로 생각했기 때문이다.
하지만 다른 분들의 풀이를 보면 가장 큰 값과 가장 작은 값을 먼저 구명보트에 실어보내는 방식이었다.
처음엔 이해가 되지 않아 반례를 생각해보았는데,
예를들어 limit = 120kg , people[]=[90,80,70,30,20,10] 으로 가정하자.
나의 방식대로라면 90+30, 80+20, 70+10 이렇게 3개의 구명보트가 필요할 것이다.
하지만 다른 분들의 방식이라면 90+10, 80+20, 70+30 으로 마찬가지로 3개의 구명보트가 필요하다.
나의 방식대로 했을 때, 첫 두 값인 90+30 이후에 항상 두 값보다 더 작은 값만이 남게 되므로, 항상 limit 보다 작음을 보장할 수 있다.
즉, 음수가 아닌 자연수 배열일 때 다른 분들의 방식과 내 방식이 결국 같은 결과를 내놓게 된다.
그리고 최솟값을 뒤에서부터 찾으면 되니까 최댓값부터 찾는 나의 방식보다 비교 횟수도 줄어든다.
public class Solution {
public int solution(int[] people, int limit) {
int answer = 0;
Arrays.sort(people);
int min = 0;
for (int max = people.length - 1; min <= max; max--){
if (people[min] + people[max] <= limit) min++;
answer++;
}
return answer;
}
'알고리즘 > 문제' 카테고리의 다른 글
| [프로그래머스] Lv2 점프와 순간이동 / JAVA (0) | 2023.03.04 |
|---|---|
| [프로그래머스] Lv2 예상대진표 / JAVA (0) | 2023.03.01 |
| [프로그래머스] Lv2 카펫 / JAVA (0) | 2023.02.27 |
| [프로그래머스] Lv2 영어 끝말잇기 / JAVA (0) | 2023.02.26 |
| [프로그래머스] Lv2 다음 큰 숫자 / JAVA (0) | 2023.02.25 |
