탐욕법(greedy) - 구명보트

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

우선 의식의 흐름대로 코드를 짜보았다.
사람들의 무게 리스트를 정렬해서 제일 먼저 태울 사람들을 묶었다.
그리고 누적된 kg이 초과되면 그룹을 자르고 다시 그룹 묶는 식으로

def solution(people, limit):
    people.sort() # 무게 정렬
    kg = 0 # 누적할 kg
    
    sub_list = []
    total = []
    idx = 0
    for idx, num in enumerate(people):
        kg += num
        #print(f"num = {num}, {kg}kg, limit = {limit}")
        if kg == limit:
            sub_list.append(num)
            total.append(sub_list)
            sub_list = []
            kg = 0
        elif kg > limit:
            total.append(sub_list)
            sub_list= []
            sub_list.append(num)
            total.append(sub_list)
            kg = 0
        else:
            if idx == len(people)-1:
                sub_list = []
                sub_list.append(num)
                total.append(sub_list)
                break
            sub_list.append(num)
    return len(total)

하지만 어림없지

슬라이싱을 통해 코드를 좀더 간결하게 해보았다.

def solution(people, limit):
    people.sort() # 무게 정렬
    kg = 0 # 누적할 kg
    
    sub_list = []
    total = []
    start = 0    
    for idx, num in enumerate(people):
        kg += num # kg 누적 
        
        if kg == limit: # 만약 limit에 딱 맞으면 그룹 나누기
            total.append(people[start:idx+1])
            sub_list, kg, start = [], 0, idx+1 # 초기화
        elif kg > limit: # 초과되어도 그룹 나누기
            total.append(people[start:idx])
            start = idx
        if idx == len(people)-1:
            total.append(people[start:])
            break
        sub_list.append(num)
    return len(total)

깔끔하게 그룹이 나눠지는 듯 함. 하지만 통과가 안되는 것은 여전히 마찬가지 .. 일단 시간초과는 안뜨긴했으니 (효율성에서 통과는 못했지만) 먼저 고려하지못한 테스트케이스에 대해서 생각해보자

질문하기에서 사람들의 질문을 찬찬히 보았다. 근데 아.. ㅋㅋㅋㅋㅋㅋㅋㅋ 다시 읽어보니 단 2명이다 ... 난독증 미쳤고 ㅎㅎ

그러면 왜 가장 큰 무게인 사람과 가장 가벼운 사람인 사람을 넣어야하는지 이해가 된다. 가장 큰 무게인 사람을 보트에 단 한명만 넣으면 너무 손해니까 어떻게든 끼역넣어야겠지..

참고한 링크

내 입맛대로 바꾸고있는데 계속 테케가 걸려서
될대로 되라 심정으로 일단 제출을 했는데 다 통과가 되었다. 않이 이게 왜 되는거지??

def solution(people, limit):
    
    people.sort() # 무게 정렬
    
    start, end = 0, len(people)-1
    boat = 0
    
    while (start <= end): # 반절을 넘기면 안됨
        if start == end : 
            boat += 1
            break
        if people[start] + people[end] <= limit:
            start += 1
            end -= 1
            boat += 1
            continue
        else:
            end -= 1
        boat += 1
    return boat

boat를 추가하는 타이밍이 애매해서 일단 닥치는대로 넣어보았다.

1. 우선 한도에 맞게 그룹이 짝지어진 경우
   boat를 추가해서 넣어주기

2. 만약 한도 초과면 따로 넣어야하니까 boat 추가해서 넣어주기..
   뭐야 결국 다 boat 추가 아닌가?;;

코드를 다시 바꿔보았다.

def solution(people, limit):
    
    people.sort() # 무게 정렬
    
    start, end = 0, len(people)-1
    boat = 0
    
    while (start <= end): # 반절을 넘기면 안됨
        boat += 1
        if start == end :
            break
        if people[start] + people[end] <= limit:
            start += 1
            end -= 1
            continue
        else:
            end -= 1
        
    return boat

어차피 보트는 항상 나가게 되어있고 거기서 인원이 1명이나 2명이냐 그 뿐인 것같다.

코드가 좀 와닿진 않긴한데.. 튼 그렇다
찝찝하게 끝났다.. ㅎㅎㅎ Lv3까지 하기엔 시간이 너무 없기때문에 Lv2까지만 풀고 그리디의 고난도 문제 풀이는 끝