프로그래머스 - 구명보트 (sol.java)

◎문제 링크

programmers.co.kr/learn/courses/30/lessons/42885?language=java#

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

---

◎문제 파악

문제의 조건:

1. 구명보트는 한 번에 최대 2명까지만 탈 수 있다.

2.  limit보다 무거운 사람들이 보트를 탈 수 없다. ex) 70kg랑 80kg의 사람은 100kg이 limit인 보트에 탈 수 없다.

---

◎첫 코드

        public int solution(int[] people, int limit) {
        	int answer = 0;
        
        	ArrayList<Integer> person = new ArrayList<>();
            //신축성이 없는 배열보다는 ArrayList가 효율적일 것 같다.
   		    for(int i = 0; i<people.length; i++){
	            person.add(people[i]);
   		    } //ArrayList에 배열 people을 넣는다
	        Collections.sort(person); //ArrayList 정렬
        
        	while(!person.isEmpty()){
            	answer++;
            	int i = person.remove(0);
            	for(int p = person.size()-1; p>=0; p--){
                	if(i+person.get(p)<=limit){
                    	person.remove(p);
                    	break;
                	}
            	}
        	}
        	return answer;
    	}

 

 

코드 동작 예시

1. people을 정렬한다

people

30

40

70

80

2. index 0 요소를 remove하고, index 0의 값과 합쳐 limit보다 작은 값을 뒤에서부터 탐색한다.

people

40

70

80

3. 70이 30과 합쳐서 100이므로 함께 삭제한다

people

40

80

4. index 0 요소를 remove하고, index 0의 값과 합쳐 limit보다 작은 값을 뒤에서부터 탐색한다.

people

80

5. 40과 합쳐서 100이하인 요소가 없다.

6. index 0 요소를 remove하고, index 0의 값과 합쳐 limit보다 작은 값을 뒤에서부터 탐색한다.

people

 

이렇게 작동하는 코드를 짜니, 효율성 테스트에서 모두 시간이 초과 되었다.

---

◎코드 개선

1. 내림차순 정렬하면 (즉, 맨 뒤에 요소를 제일 먼저 살펴보면)  

"index 0의 값과 합쳐 limit보다 작은 값을 뒤에서부터 탐색한다."의 과정이 생략된다.

 

ex) [20,80,90] limit = 100일 경우

20부터 쳐다보면 20+90>=100인지, 20+80>=100 인지 살펴보아야 하지만,

90부터 쳐다보면 90+20>100이므로, 20 다음의 숫자도 100을 넘을 것이라는 것을 알 수 있다.

 

2. limit/2 보다 작은 값이 나오면, 그 인덱스부터는 무조건 2명씩 보낼 수 있다.

 

ex) [20,20,20,20,20,80] limit = 100일 경우

1. 80과 20이 사라지고, [20,20,20,20] 이 남는다

2. 이때 맨 끝 인덱스의 값 20 < 100/2이고, 20 앞 값들은 모두 20보다 작거나 같으므로,

남은 4명을 무조건 2명씩 태워서 보낼 수 있다.

 

3. ArrayList 쓰지 않기

배열을 ArrayList에 넣은 과정은 시간 복잡도 Olog(n)을 가지므로, 필요 없을 경우에는 쓰지 않는 게 옳다.

 

개선한 코드:

	public int solution(int[] people, int limit) {
        int answer = 0;
        Arrays.sort(people); //배열 정렬, ArrayList 사용x
        //ArrayList를 사용하지 않았으므로, 탐색할 부분을 정해주는 변수 k와 j 도입
        int k = people.length-1;
        int j = 0;
        
        while(k>=j){
            int i = people[k]; //뒤에서부터 살펴보기
            if(i<=limit/2){ 
            //어떤 값이 limit/2보다 작거나 같으면 그 값부터는 무조건 2명씩 보낼 수 있음
                if((k-j+1) % 2==0){
                    answer = answer + (k-j+1)/2;
                }else{
                    answer = answer + (k-j+1)/2+1;
                }
                break;
            }
            k--;
            answer++;
            if(k>=j && people[j]+i<=limit){
                j++;
            }
            
        }
        
        
        
        return answer;
    }

코드를 개선하니, 다행히 효율성 테스트를 통과하였다.

불필요한 반복을 줄이고, 현 상황에 가장 잘 맞는 자료구조를 쓰는 것이 얼마나 중요한지 알게 되었다.

---

◎ 다른 사람의 풀이

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; //전체 사람의 수 - 두명이서 탄 횟수 = 보트의 개수
    }
}

엄청 깔끔하고 효율적이다.. 코드 잘 짜는 사람들이 이렇게 많구나 싶다.