[Java][LeetCode] #881. Boats to Save People | O(n+k) | O(nlogn)

오늘은 랜덤문제 풀기~

몸이 안좋아서 그냥 안하고 자려다가 한 문제 정도 풀기위해 앉았다!

근데 생각보다 오래걸렸다..ㅠ

 

문제 / 예제 / 제한조건

내가 처음에 문제를 제대로 안읽어서 놓친 부분이 있었는데 바로

동시에 2명만 한 배에 탈 수 있다는 조건이다.

 

그리고 나는 혼자서 순서가 바뀌면 안된다고 생각했다.

왠지 모름..

 

그래서 만약에 3 5 3 4 가 있으면

3->5->3->4 순서대로 배에 타야해서 4대의 배가 필요하다고 생각했다.

 

그래서 푼 풀이는

#풀이 1 

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        int numberOfBoats = 1;

        int currentRemainPeople = limit - people[0];
        for (int i = 1; i < people.length; i++) {
            if(currentRemainPeople == limit) {
                numberOfBoats++;
                currentRemainPeople -= people[i];
            }
            else if (currentRemainPeople >= people[i]) {
                currentRemainPeople -= people[i];
            } else {
                currentRemainPeople = limit;
                numberOfBoats++;
            }
        }

        return numberOfBoats;
    }
}

 

이렇게 풀었는데, 당연히 틀렸다.

 

#풀이 2

아~ 순서를 바꿔서 타도 되는구나!

라는 깨달음을 얻고 푼 풀이 2번째

근데 이번에는 2명이 한 배에 탈 수 있는 최대 인원이라는 생각을 못하고 풀었다.

 

풀이 방식은

1. 무게 배열 정렬

2. 가장 무거운 무게 + 가벼운 무게 + 가벼운 무게2 ... 이렇게 해서 최대 보트 찾기

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        int numberOfBoats = 1;

        Arrays.sort(people);

        int leftIndex = 0, rightIndex = people.length - 1;
        int currentRemainPeople =  limit - people[rightIndex--];
        while(leftIndex <= rightIndex) {
            if(currentRemainPeople >= people[leftIndex]) {
                currentRemainPeople -= people[leftIndex];
                leftIndex++;
            } else {
                currentRemainPeople =  limit - people[rightIndex--];
                numberOfBoats++;
            }
        }

        return numberOfBoats;
    }
}

 

그렇게 했을 때, 실패!

보트에는 2명씩만 타야해!~

이것을 알아채지 못하고 있다가

Discuss를 보는데, 나랑 같이 의문점을 갖고 있는 사람이 있어서 알아 낼 수 있었다 ㅎ

댓글에 2명씩만 타야되는데 너는 지금 3명씩 타고 있는 배가 있잖아~ 라고 해줘서 알았음

 

그렇게 내 최종 풀이

 

#풀이 3

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        int numberOfBoats = 1;

        Arrays.sort(people);

        int leftIndex = 0, rightIndex = people.length - 1;
        int currentRemainPeople = limit - people[rightIndex];
        while (leftIndex < rightIndex) {
            if (currentRemainPeople >= people[leftIndex]) {
                leftIndex++;
                rightIndex--;
                if(leftIndex <= rightIndex) numberOfBoats++;
                currentRemainPeople = limit - people[rightIndex];
            } else {
                rightIndex--;
                currentRemainPeople = limit - people[rightIndex];
                if(leftIndex <= rightIndex) numberOfBoats++;
            }
        }

        return numberOfBoats;
    }
}

양쪽 케이스 모두 보트의 갯수를 올리고, 대신 작은 쪽/큰쪽 인덱스를 양쪽 다 움직일 것인지, 한 쪽만 움직일 것인지를 달리해줬다!

TimeComplexity : O(n log n) 
SpaceComplexity : O(1)

 

 

#풀이 4

내가 이 전에 생각했던 방식 중에 HashMap에 해당 weight와 weight 갯수를 저장 한 뒤 하는 방법을 생각해보았다.

구현하다보니 너무너무 복잡해져서 포기했었는데,

생각해보니 배열로 그냥 하면 되는 것 이었다!!!!

왜냐하면 limit 가 최대 수 이기 때문!!

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        int numberOfBoats = 0;

        int[] weights = new int[limit+1];
        for(int person : people) {
            weights[person]++;
        }

        int leftIndex = 0, rightIndex = weights.length - 1;
        while(leftIndex <= rightIndex) {
            while(leftIndex < rightIndex && weights[leftIndex] <= 0) leftIndex++;
            while(leftIndex < rightIndex && weights[rightIndex] <= 0) rightIndex--;

            if(weights[leftIndex] <= 0 && weights[rightIndex] <= 0) break;
 
            int sumWeight = leftIndex + rightIndex;

            numberOfBoats++;
            if(sumWeight <= limit) {
                weights[leftIndex]--;
            }

            weights[rightIndex]--;
        }

        return numberOfBoats;
    }
}

Time Complexity : O(n + k)
Space Complexity : O(k)
* K = limit value