Today's Algorithm(2019-01-01)

programmers. 구명보트

남들은 다 쉽게 푸는것 같은데 저는 왜 이렇게 그리디 문제가 감이 안올까요..

 

처음엔 우선순위큐를 사용하여 가장 작은 몸무게를 찾은 다음 남은 사람들 중 무게제한을 초과하지 않는 사람들 중 가장 무거운 사람을 골랐습니다. 아무래도 남은 사람들 중 가장 무거운 사람을 찾는 과정에서 복잡도가 증가하였고 여러 테스트케이스에서 통과하지 못하였습니다.

 

이렇게 제일 큰 것 찾고 가장 작은 것도 동시에 찾기 위해선 우선순위큐 대신 리스트를 사용하고 포인터를 2개를 사용하면 됩니다(다 풀고나서 다른 사람들의 풀이를 보니 Deque도 많이 사용했더라구요. 어차피 똑같은 맥락이죠). 리스트를 오름차순 정렬하고 가장 작은(왼쪽) 수의 인덱스를 왼쪽(left), 가장 큰(오른쪽) 수의 인덱스를 오른쪽(right)에 두고 while(left < right) 인 경우엔 한해 계속 반복하는 것입니다.

여기서 포인트는 가장 작은 수와 가장 큰 수가 짝이 될때 가장 효율적이라는 점(문제에서 최대 2명 밖에 탈 수 없다고 가정)입니다. 혼자 타는 경우가 있는데요. left 수와 right 수의 합이 무게제한을 넘을 때이겠죠. 이때는 right 만 조용히 -1 해줍니다. 만약 left 수와 right 수의 합이 무게제한을 안 넘을 때는 환상의 짝궁인 것입니다. 이때는 count 를 +1 해주고 다음 경우를 위해 left++, right-- 을 해줍니다. 그렇게 하여 마지막 답은 people.length() - count 인데요. 그 이유는 환상의 짝궁이 된 수는 지워야 딱 나오거든요. 조금만 생각해보면 알 것입니다.

class Solution {
    public int solution(int[] people, int limit) {
        List<Integer> list = new ArrayList();
        for (int person : people) {
            list.add(person);
        }
        Collections.sort(list);

        int left = 0;
        int right = list.size() - 1;
        int count = 0;

        while(left < right) {
            if(list.get(left) + list.get(right) <= limit) {
                count++;
                left++;
                right--;
            } else {
                right--;
            }
        }
        return people.length - count;
    }
}

 

위 코드는 이 블로그를 참고하여 작성되었습니다. 작은 수와 큰 수를 동시에 알아야할 때 정렬 후 포인터를 2개를 동시에 사용 또는 Deque를 사용할 수 있다는 생각을 못했네요.. 다음엔 잘 활용할 수 있기를...!