[프로그래머스][Java][Lv.2] 구명보트 - 투포인터

 

https://school.programmers.co.kr/learn/courses/30/lessons/42885

프로그래머스

 

해당 문제는 그리디 알고리즘을 이용한 문제라고 되어있지만,

나는 투 포인터를 배웠기 때문에 투포인터로 풀어보고자 한다.

 

첫번째 풀이

테스트케이스는 다 성공하지만,  제출했을 때, 결과가 처참하다.

단지 포인터를 쓰기 위해 lt rt만 집중했고, 문제를 어떻게 해결해야할지 판단과  문제에 대한 분석이 미숙했던것 같다.

채점 결과

정확성: 14.8

효율성: 7.4

합계: 22.2 / 100.0

 

import java.util.Arrays;

public class Solution1 {
    public int solution(int[] people, int limit) {
        int answer = 0;
        int ch[] = new int[people.length];
        int used[] = new int[people.length];

        Arrays.sort(people); // 50 50 70 80
        int sum = 0, lt = 0;
        for (int rt = 0; rt < people.length; rt++) {
            sum += people[rt];
            used[rt] = 1;
            if (sum == limit){
                for (int i = 0; i < used.length; i++) {
                    if (used[i] == 1) ch[i] = 1;
                }
                answer ++;
            }
            while(sum > limit) {
                sum -= people[lt++];
                if (sum <= limit) {
                    answer ++;
                    ch[rt] = 1;
                }
            }
        }
        for (int i = 0; i < ch.length; i++) {
            if (ch[i] == 0) {
                answer++;
            }
        }
        return answer;
    }
    public static void main(String[] args) {
        Solution1 T = new Solution1();
        int[] people1 = {70, 50, 80, 50};
        int[] people2 = {70, 80, 50};
        int limit= 100;
        System.out.println(T.solution(people1, limit));
    }
}

 

두번째 풀이

import java.util.Arrays;
class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        Arrays.sort(people); // 무게 순으로 정렬

        int lt = 0, rt = people.length - 1;

        while (lt <= rt) {
            // 가장 가벼운 사람과 가장 무거운 사람을 선택
            int lightest = people[lt];
            int heaviest = people[rt];

            if (lightest + heaviest <= limit) {
                // 가장 가벼운 사람과 가장 무거운 사람을 함께 태울 수 있는 경우
                lt++;
                rt--;
            } else {
                // 가장 무거운 사람만 태울 수 있는 경우
                rt--;
            }

            answer++;
        }

        return answer;
    }
}

정확성 테스트

테스트 1 〉	통과 (2.12ms, 83.4MB)
테스트 2 〉	통과 (0.96ms, 77.1MB)
테스트 3 〉	통과 (1.83ms, 66.1MB)
테스트 4 〉	통과 (1.87ms, 75.1MB)
테스트 5 〉	통과 (1.29ms, 79MB)
테스트 6 〉	통과 (0.95ms, 75.9MB)
테스트 7 〉	통과 (0.85ms, 74.1MB)
테스트 8 〉	통과 (0.37ms, 74.6MB)
테스트 9 〉	통과 (0.46ms, 72.6MB)
테스트 10 〉	통과 (1.23ms, 74.5MB)
테스트 11 〉	통과 (1.75ms, 78.3MB)
테스트 12 〉	통과 (1.69ms, 72.5MB)
테스트 13 〉	통과 (1.54ms, 72.6MB)
테스트 14 〉	통과 (0.94ms, 83.6MB)
테스트 15 〉	통과 (0.61ms, 74MB)
테스트 16 〉	통과 (0.57ms, 76.2MB)
테스트 17 〉	통과 (0.52ms, 81MB)
테스트 18 〉	통과 (0.41ms, 73.5MB)
테스트 19 〉	통과 (0.36ms, 81MB)
테스트 20 〉	통과 (0.36ms, 75.5MB)
테스트 21 〉	통과 (0.55ms, 75MB)
테스트 22 〉	통과 (0.55ms, 72.6MB)

효율성 테스트

테스트 1 〉	통과 (10.26ms, 56MB)
테스트 2 〉	통과 (8.65ms, 53.6MB)
테스트 3 〉	통과 (11.27ms, 56.2MB)
테스트 4 〉	통과 (6.93ms, 53.5MB)
테스트 5 〉	통과 (8.85ms, 53.7MB)