[Level 2] 구명보트

코딩테스트 연습 - 구명보트

 

def solution(ppl, lim):
    ppl.sort()

    cnt = 0

    while ppl:
        if len(ppl) == 1:
            cnt += 1
            break
    
        cur_cnt = cnt
    
        for i in reversed(range(1, len(ppl))):
            if ppl[0]+ppl[i] <= lim:
                ppl.pop(0)
                ppl.pop(i-1)
                cnt += 1
                break
            
        if cnt == cur_cnt:
            ppl.pop(0)
            cnt += 1
    
    return cnt

 

▷ 위의 코드를 작동시킬 경우, 효율성 측면에서 문제가 발생한다. 왜냐하면 pop 함수를 사용하였기 때문이다. 따라서 이를 개선하기 위해서는 인덱스를 사용하여야 한다.

 

▷ 위의 코드의 다른 문제점은 이중루프를 돌렸다는 것이다. 아래의 코드를 보면 알겠지만, 이중루프를 돌릴 필요가 없는 문제이다.

 

▶ pop 함수의 첫 번째 인자는 해당 리스트에서 빼고자 하는 대상의 위치를 의미한다.

 

▶ 아래의 코드는 인덱스를 사용하여 문제의 논리를 구현하였다.

 

def solution(ppl, lim):
    ppl.sort()
    cnt = 0
    
    s, e = 0, len(ppl)-1
    
    while s <= e:
        cnt += 1
        
        if ppl[s]+ppl[e] <= lim:
            s += 1
        e -= 1
        
    return cnt