[알고리즘] 프로그래머스 구명보트 - Python

문제 : 프로그래머스 구명보트 문제

프로그래머스

 

처음에는 투포인터를 사용하지 않고 구현을 했다. 이 경우에는 O(n^2)의 시간복잡도를 가지기 때문에 시간 초과 문제가 발생했다. 

def solution(people, limit):
    answer = 0
    people.sort(reverse=True)
    end=len(people)-1
    for i in range(len(people)):
        if i >end: break
        if people[i]>limit-40:
            answer+=1
            continue
        for j in range(end, i,-1):
            if people[i]+people[j]<=limit:
                end=j-1
                break
        answer+=1
    return answer

 

먼저 people 배열을 내림차순으로 정렬하고, 최대치와 최소치를 더한값을 비교하여 answer를 구해나간다. 시간초과를 해결하기 위해서 end 변수를 추가하고, limit - 40을 넘는 경우에는 패스하도록 하였지만 2개의 효율성 테스트 항목을 만족하지 못했다. 근본적으로 이 방법이 시간 복잡도 측면에서 효율이 좋지 않다는 것을 알게되었다.

해결 방법 : 투포인터

투포인터를 사용하게 되면 left 인덱스와 right 인덱스를 설정해야한다. 초기 설정은 left는 0번 인덱스, right는 가장 오른쪽 인덱스를 넣어둔다. 조건에 따라서 계속해서 l과 r 인덱스를 조정해나가면서 O(n) 의 시간복잡도로 구현이 가능하다. 

def solution(people, limit):
    answer = 0
    people.sort(reverse=True)
    l=0
    r=len(people)-1
    while l <=r:
        if people[l]+people[r]<=limit:
            answer+=1
            l+=1
            r-=1
            continue
        else:
            l+=1
            answer+=1
    return answer

 

여기서 더 개선을 해보자면 while 안에서 l 인덱스는 어떤 경우에도 +1을 하기 때문에 조건 밖으로 빼고 while 문 첫 문장으로 넣어도 좋을거 같다.