2021-01-14] Boats to Save People

오늘의 문제:

leetcode.com/explore/challenge/card/january-leetcoding-challenge-2021/580/week-2-january-8th-january-14th/3602/

Explore - LeetCode

 

문제에 대해서 간단히 생각할땐 쉬웠는데, 막상 파고드니 어려워 죽는줄..

 

문제 예시를 보며 이해해보자.

 

<문제 예시 1-3>

 

입력값으로 people이 주어지고, 이 list의 원소값들이 한 사람당의 무게라고 생각한다.

이를 보트에 태우는 것으로 보트의 한도무게는 limit로 주어지며, 이를 이용하여 보트가

최소 몇대 필요한지 최소 값을 반환한다.

 

예시 2번을 보면,

총 4명의 사람이 3,2,2,1 무게를 가지고 있고, 보트의 한도무게는 3

1) 1,2 의 무게를 지닌 사람들로 1 보트

2) 3의 무게를 지닌 사람으로 2 보트

3) 마지막 2의 무게를 지닌 사람으로 3보트

 

총 3대의 보트를 이용해야 최소한으로 보트를 이용하게 된다.

 

이를 구현을 위해 생각했을 때, 나는 처음 people의 값을 정렬하고 뒤로 하나씩 비교하여,

한도의 값을 채워준다면 해결된다고 생각했다. ( 오? 나름 괜찮은데? )

암! 어림도 없지!!

장렬히 실패..

<실패한 케이스>

위에서 처럼 역순 정렬로 큰 순서로 비교하며 limit를 찾았지만, 5,1이 같이 탄다면 3대가 아닌 2대로 가능했다..

 

문제풀이 1차 실패)

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        cnt=0
        people.sort(reverse=True)
        ans=[]
        length=len(people)
        checkval=0
        temp=[]
        for i in range(length):
            temp.append(people[i])
            checkval=checkval+people[i]
            print('temp is {} / checkval is {} / ans is {}'.format(temp,checkval,ans))
            if limit > checkval:
                print('limit > checkval')
                continue
            elif limit == checkval:
                print('limit == checkval')
                ans.append(temp)
                temp=[]
                checkval=0
            else:
                print('limit < checkval')
                temp.remove(people[i])
                for idx in range(i+1,length):
                    if limit > checkval+people[idx]:
                        continue
                    elif limit == checkval+people[idx]:
                        temp.append(people[idx])
                        ans.append()
                        
                ans.append(temp)
                temp=[people[i]]
                checkval=people[i]
        if ans == []:
            return 1
        if temp != []:
            ans.append(temp)
        print(i,length)
        print(ans)
        return(len(ans))

 

나의 잘못은 무게가 큰순서로 비교한거 까지는 좋았으나, 한도가 작았을때, 작은 값을 넣어 확인하지 않은 것이 틀린 이유 같다.

 

동기의 문제 풀이로 설명해보자.

 

문제풀이 2차) (feat. 동기의 도움)

 

큰 값 순으로 정렬하고,  ( 여기까지는 동일함 )

큰 값이 한도값보다 작으면, 작은 값을 채워보며 limit를 맞춘다. ( 이부분을 나는 큰값을 채워가며 문제발생 )

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people.sort(reverse=True)
        cnt = 0
        left = 0
        right = len(people)-1
        while left<=right: # 종단 조건
            remain = limit - people[left] # 무게가 큰 순서부터 한도무게를 줄어 남은 무게
            #print(people[left], remain)
            left += 1 # 다음 큰 무게를 위한 shift
            if remain > 0 and people[right] <= remain: # 작은 무게가 남은 무게와 동일할시
                #print(people[right])
                right -=1 # 작은 무게를 지운다.
            cnt += 1 # 한도무게가 차서 보트 수를 늘린다.
        return cnt