[문제 풀이] 구명보트 LV 2.

요구사항

문제 풀이 1차

def solution(people, limit):
    answer = 0
    people = sorted(people)
    while people:
        if len(people) == 1:
            return answer + 1
        popSum = people[0] + people[-1]
        if popSum <= limit:
            people.pop(0)
        people.pop()
        answer += 1
    return answer

• 1차적으로 people Array값을 sort를 통해서 순서를 정렬해주고 그 후에 맨처음값과 마지막 값을 더했을때 만약 마지막 값이 limit 값을 초과 한다면 마지막 값을 pop해주고 다시 맨처음값과 마지막 값이 limit 값과 같거나 또는 작다면 둘다 pop 처리 해주는 식이다.

위처럼 문제를 푸는 접근 방식은 맞지만 시간 복잡도 측면에서 while 루프 안에서 pop을 하게 되면 O(n^2)의 시간복잡도를 가지게 된다는 점이다. 이를 보안해야 한다.

문제 풀이 2차 - 투 포인터(Two Pointer) 방식

def solution(people, limit):
    answer = 0
    people = sorted(people)
    left, right = 0, len(people) - 1
    while left <= right:
        if people[left] + people[right] <= limit:
            left += 1
        right -= 1
        answer += 1
    return answer

letf와 right에 0번째와 배열의 마지막 인덱스 값을 넣어주고 가장 왼쪽값과 오른쪽 값을 더해서 limit값 보다 작거나 같으면 left값을 한칸 옆으로 옴겨주고, right값도 한칸 옮겨준다 반대로 limit 값보다 크다면 left값은 그대로 두고 right값만 한칸 이동시켜 주게 되면 시간복잡도는 O(nlogn)이 된다.