[Java/프로그래머스/탐욕법] Level 2 : 구명 보트

문제

programmers.co.kr/learn/courses/30/lessons/42885

코딩테스트 연습 - 구명보트

 

처음 생각했던 방법(걍 틀림)

우선순위 큐에 넣어서 작은 것들부터 묶으려고 했다.

 

하지만 이 경우 people = {30, 40, 60, 70}, limit=100 일 때 (30,40) / 60 / 70 으로 3이 리턴된다.

옳은 답은 (70,30) / (60, 40) 으로 2가 리턴되어야 한다.

 

두번째로 생각한 방법 ( 효율성 테스트: 실패(시간초과))

두번째는 그럼 내림차순으로 하면 되겠다 싶었다.

위의 경우에서 pos가 70을 가리킬때, 나머지 원소를 쭉 훑으면서 합쳤을때 100 이하면 된다.

해당되는 원소들은 0으로 바꿔줬다.

마지막에 어느 것에도 더해질 수 없는 경우 그 원소의 개수만큼 answer 값을 증가시켰다.

 

정확도 100.0

효율성 0.0

import java.util.Arrays;
class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        
        Arrays.sort(people);
        
        int pos=people.length-1;
        while(pos>-1){
            if(people[pos]==0){
                --pos;
                continue;
            }
            for(int i=pos-1;i>-1; i--){
                if(people[pos]+people[i]<=limit && people[i]!=0){
                    ++answer;
                    people[pos]=0;
                    people[i]=0;
                    break;
                }
            }
            --pos;
        }
        
        for(int weight : people){
            if(weight > 0){
                ++answer;
            }
        }
        
        return answer;
    }
}

 

 

 

성공 코드

아이디어 주신 지원늼 감사합니다ㅠㅠㅠ 속터져 죽는 줄

오름차순으로 정렬한 뒤 pos와 lPos로 양 끝을 가리키는 변수를 지정했다.

양 끝에서 하나씩 비교하면서 좁히는 방식이다.

이렇게 하면 이중 for문을 쓰지 않아도 되서 훨씬 시간이 단축된다!

 

lPos는 배열의 왼쪽(가장 작은 값을 가리킴), pos는 배열의 오른쪽(가장 큰 값을 가리킴)에서 시작한다.

pos가 기준이다.

 

예1

50 50 70 80

50+80 > limit(100) 이므로 80 하나만 나간다. → 1번

50+70 > limit 이므로 70만 나간다. → 1번

50+50 == limit 이므로 함께 나간다 → 1번

 

* 여기서 한번에 두명만 나갈 수 있다 했으므로 이런 로직이 가능한 것이다.

* 어차피 50이 가장 작고 80이 가장 크다 → 둘의 합이 limit보다 크다면, 50보다 큰 수로는 80과의 합이 limit 이하일 수가 없다.

 

예2

50 70 80

80 → 1번

70 → 1번

50 → 1번

여기서 생각해보면 pos만 계속 작아지므로 lPos==pos인 경우도 고려했어야 했다.

 

import java.util.Arrays;
class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        
        Arrays.sort(people);
        
        int lPos = 0;//작은 값을 가리키는 인덱스
        int pos = people.length-1;//큰 값을 가리키는 인덱스
        while(lPos<=pos){
        	if(people[pos]+people[lPos]<=limit){
                people[pos--]=0;
                people[lPos++]=0;
            }else{
            	people[pos--]=0;
            }
            ++answer;
        }
        return answer;
    }
}