[프로그래머스] lv2. 구명보트 [#투포인터]

 

 

 

---

1. 출처

---

 

프로그래머스

 

오늘은 지연이가 풀라고 추천해준 구명 보트 문제를 풀었다.

마침 최근에 투포인터를 공부해서 이걸 이용해 풀었다.

 

 

---

2. 설계

---

 

 

설계는 간단하다. 

[70, 50, 80, 50]

100

3

 

이런 예제가 있다고 가정하자.

 

 

1) 사람들의 몸무게를 sort한다.

Arrays.sort(people)

 

그럼 [50, 50, 70, 80] 이렇게 될 것이다.

 

 

2) 투포인터를 이용하자

 

start 포인터는 0번 인덱스부터 시작하고, end 포인터는 length-1 위치부터 시작한다.

 

if) people[start] + people[end] > limit count

이 경우는 구명보트를 people[end] 혼자만 타야한다는 의미이다.

end 포인터가 가리키는 인덱스에 방문처리를 하고, count++를 해준다. 그리고, end 포인터를 앞으로 이동시킨다.

 

if) people[start] + people[end] == limit count

이 경우는 구명보트를 people[start]와 people[end] 함께 탈 수 있다는 의미다.

end 포인터가 가리키는 인덱스에 방문처리를 하고, count++를 해준다. 그리고, end 포인터를 앞으로 이동시킨다. 여기까지는 위와 똑같은 과정이다.

 

하지만 다른점은 start를 한 칸 뒤로 전진시킨다는 점이다.

 

 

if) people[start] + people[end] < limit count

이 경우도 구명보트를 people[start]와 people[end] 함께 탈 수 있다는 의미다. == 경우와 그냥 똑같다.

 

 

즉, 가장 가벼운 애와 가장 큰 애 조합을 만들겠다는 의미다. 그럼 최소 경우의 수가 나온다.

 

 

---

3. 전체 코드

---

 

import java.util.Arrays;

class Solution {
    public int solution(int[] people, int limit) {
        
        Arrays.sort(people); // 50 50 70 80
        
        int count = 0;
        int E = people.length-1;
        boolean[] sel = new boolean[people.length];
        
        for(int S=0;S<people.length;S++){ //시작점
            
            while(S<E){
                
                count++;
                sel[E] = true;
                E--;
                
                if(people[S]+people[E+1] <= limit){
                    sel[S] = true;
                    break;
                }
            }
            
            if(S==E && !sel[S]){//수렴 완료
                count++;
            }
            
        }// for end
        
       return count;
    }
}