문제

https://programmers.co.kr/learn/courses/30/lessons/42885

나의 코드 (답안참조)

"""
1. 아이디어

2. 시간복잡도

"""

def solution(people, limit):
    
    people.sort(reverse=True)
    answer = 0
    
    lp, rp = 0, len(people)-1
    
    while lp <= rp:
        weight_sum = people[lp]
        answer += 1
        
        if weight_sum + people[rp] <= limit:
            rp -= 1
        
        lp += 1
        
    return answer
    

def solution(people, limit):
    
    people.sort()
    answer = 0
    lp, rp = 0, len(people)-1
    
    while lp <= rp:
        weight = people[rp]
        
        if weight + people[lp] <= limit: # 2명만 보트에 탈 수 있으므로 가능한 풀이
            lp += 1
        
        rp -= 1
        answer += 1
        
    return answer

설명

위의 문제의 핵심은 그리디와 투포인터라고 할 수 있습니다.

일단 문제에서 최적의 답을 찾기 위해서 내림차순으로 정렬이 필요 합니다. 그 이유는 몸무게가 큰 순으로 시작해야 문제에서 원하는 최적의 해를 그리디 답게 풀 수 있기 때문입니다.

그리고 투 포인터를 써서 제일 몸무게가 많이 나가는 사람과 적게 나가는 사람의 합을 통해 limit보다 작은지 확인하여 포인터를 이동시켜 줍니다.

2023-04-17) 꼭 내림차순 정렬은 안해도됨

참고자료

X