[Greedy] 프로그래머스 - 구명보트

해결포인트✨

1. 가장 무거운 사람이 보트를 탔다고 가정하고, 가장 가벼운 사람이 함께 탈 수 있는지 여부를 먼저 확인해 연산량을 줄이는 것이 핵심이었다.

 

2. 처음에 queue로 풀었는데, 가장 가볍지 않은 사람이 보트를 탈 수 있는 경우의 연산이 많아져 효율성테스트를 통과하지 못했었다.

 

3. pop 연산을 사용해 리스트를 변형하는 대신에, 리스트를 정렬한 후 인덱스가 '가장 가벼운 사람'과 '가장 무거운 사람'을 가리키도록 지정해 인덱스만 변경하면 되도록 코드를 바꿨더니 테스트를 통과했다.

 

---

시도 1 코드✨

정답은 맞았으나 효율성테스트를 통과하지 못한 초기 코드다.

def solution(people, limit):
    count=0
    people.sort()
    while len(people)>0:
        first = people.pop()
        count+=1
        if len(people)==0:
            break
        if people[-1]+first<=limit:
            people.pop()
            continue
        heaviest = -100
        for i in range(len(people)):
            if people[i]+first>limit:
                heaviest = i-1
                break
        if heaviest !=-1:
            people.pop(heaviest)
    return count

 

 

최종 코드✨

효율성도 높아지고, 코드도 한결 간결해졌다.

def solution(people, limit):
    count=0
    people.sort()
    lightest = 0
    heaviest = len(people)-1
    while lightest <= heaviest:
        if people[lightest]+people[heaviest]<=limit:
            lightest+=1
        count+=1
        heaviest-=1
    return count