99클럽 코테 스터디 16일차 TIL : 구명보트

 

 

오늘의 구명보트 문제는 테스트 케이스를 보고 접근해서 잘못된 방향으로 풀고 다시 사고를 고쳐나가는 과정이 있었다.

 

우선 테스트케이스만 봤을때는 오름차순으로 정렬하고 앞에서 둘의 합이 최대를 넘지 않으면 pop 두번, 넘는 순간부터는 한번씩 pop을 하자고 생각했는데 무엇보다 시간초과가 발생했고 아래의 케이스에서는 최적의 값을 도출할 수 없었다.

 

+ 엣지 케이스까지는 아니지만 내 풀이의 반례)

[20,30,50,60,70,80] 의 경우 => 4가지 를 만족해야하지만 내 풀이대로라면 

(20,30), 50, 60, 70, 80 으로 5가지라는 오답이 나온다.

 

따라서 sorting을 한 후에 투포인터로 접근해보았다.

최대한 limit에 가깝게 만드는게 좋으니 양 끝값을 더해서 limit을 초과한다면 오른쪽 끝, 즉 max를 버리는게 좋다고 판단하였다.

 

from collections import deque
def solution(people, limit):
    people.sort()
    answer = 0
    
    # 투 포인터
    p1 = 0
    p2 = len(people) -1
    
    while(p1 <= p2):
        if people[p1] + people[p2] <= limit:
            p1 += 1
        
        # 초과 시 가장 끝 값을 버리자!
        p2 -= 1
        answer += 1
    return answer