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

프로그래머스 고득점키트 Greedy lv1 구명보트

 

• 구명보트는 2명씩만 탈 수 있고, limit을 넘어서는 안됨
• 처음에는 그냥 sort한 배열을 이용해서 마지막에서 2개씩 끊어서 쓰려고 했음
  • 마지막에서 2개 끊어서 limit보다 작으면 둘 다 보내고, limit보다 크면 1명 보내고
  • 근데 테케, 효율성 50%만 통과함
• 이건 투포인터라는 기법을 써야 됨. 두 개의 값을 저장해서 계속 업데이트
  • 가장 작은 값+가장 큰 값을 매칭해서 태워보내는 방식
  • left=0(가장 작은 값), right = len(people)-1 (가장 큰 값)
  • left<=right 관계가 유지될 때까지
    • 만약 가장 작은 값+가장 큰 값이 limit 이하이면 태울 수 있음
      • 그럼 작은 값을 1 증가시킴
    • 만약 태울 수 없으면 if문 밖으로 빠져 나오는데, 무거운 사람만 태워보냄(작은값 그대로)
    • 누굴 태워보낼지 정했으면 answer에 1을 더해서 보트 사용량을 증가시킴

def solution(people, limit):
    answer = 0
    # print(people)
    people=sorted(people)
    # print(people)
    # 투 포인터. 가장 가벼운 사람, 무거운 사람
    left = 0
    right = len(people)-1
    while left<=right:
        if people[left]+people[right]<=limit:
            left+=1
        right-=1
        answer+=1
    return answer