[그리디] 구명보트 - Java코드 ★★

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

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

 

문제

 

설계

정렬된 자료에서 몸무게가 높은 순서로 뽑으면서 Count하되,

제일작은 사람과의 합이 limit을 넘지않으면 같이 뽑을 수 있도록,

Deque 자료구조를 활용하여, 정렬된 자료에서 앞뒤로 poll()을 해주도록 하였다

 

풀이

    public static int solution(int[] people, int limit) {
        int ans = 0;
        ArrayDeque<Integer> dq = new ArrayDeque<Integer>();
        Arrays.sort(people);        
        for(int i : people)
        	dq.add(i);
        
        while(!dq.isEmpty()) {
        	if(dq.peekFirst()+dq.pollLast()<=limit &&!dq.isEmpty())
        		dq.pollFirst();        	
        	ans++;
        }
        return ans;
    }

 

포인트

데크의 활용은 코드를 심플하게 할 뿐 아니라, 효율성을 극대화시킨다.

적절한 자료구조를 잘 알고있으면서, 활용하는게 참 중요한것 같다.

 

두번째는 검사문에서부터 제거하며 Count진행을 하는것!

그때 가장큰 값을 제거하고나서 데크가 비어있지는 않은지 한번더 체크해야 NullPointException을 막을수 있다.

 

다른사람의 풀이

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;
    }

자료구조마저 사용하지않고,

배열을 정렬해서 그냥 푸셨다.