[99클럽 코테 스터디 19일차 TIL] 구명보트 - Java [자바][프로그래머스]

 

 

📜 문제 내용

 

🤔 과정

• 구명보트에는 어차피 최대 2명까지 탑승 가능하므로, 통 안에 큰 자갈을 넣고 작은 자갈을 넣듯, 몸무게가 무거운 사람부터 넣고, 작은 사람을 넣을 수 있는 지를 판단해야겠다고 생각했다. 
• 그럼 people 배열을 오름차순으로 정렬하고 시작해야겠다고 판단했다. 
• "사람들을 구출할 수 없는 경우는 없습니다."를 통해 무거운 사람을 넣으면 바로 boat 갯수를 1 증가 시키고 작은 사람을 넣을 수 있는 지 여부를 판단하게 해야겠다고 생각했다. 

 

✨ 최초 제출 답안 - 🤦‍♂️ 효율성 실패

import java.util.*;

class Solution {
    public int solution(int[] people, int limit) {
        int totalBoat = 0;
        Arrays.sort(people);
        int peopleCnt = people.length;
        
        // 탈출 여부 boolean 배열
        boolean[] escape = new boolean[peopleCnt];

        for(int i = peopleCnt - 1; i >= 0; i--){
        	// 이미 탈출했다면 패스
            if(escape[i]) continue;
            
            escape[i] = true;
            totalBoat++;

            for(int j = 0; j < i; j++){
            	// 탈출하지 않았고, 무게 제한 안에 들면
                if(!escape[j] && people[i] + people[j] <= limit){
                    escape[j] = true;
                    break;
                }
            }
        }

        return totalBoat;
    }
}

 

이중 for문의 당연한 결과

• 테스트 케이스 문제는 모두 통과했지만, 이중 for 문으로 너무 Greedy 하게 푸는 바람에 효율성 테스트에서 모두 통과하지 못했다. 

 

✍️ 재제출 답안

import java.util.*;

class Solution {
    public int solution(int[] people, int limit) {
        
        int totalBoat = 0;
        Arrays.sort(people);

        // 투 포인터
        int i = 0;
        int j = people.length - 1;

        while(i <= j){
            
            // 구명보트는 최대 2명씩 탈 수 있다. 
            if(people[i] + people[j] <= limit){
                i++;
            }
            
            j--;
            totalBoat++;
        }

        return totalBoat;
    }
}

 

• 투 포인터를 통해 하나의 반복문으로 바꾸어 풀이했더니 효율성 테스트까지 모두 통과했다. 

 

🔗 문제 링크

• 프로그래머스 - 구명보트 (링크) 

프로그래머스