[Python/코테] 프로그래머스 구명보트

[프로그래머스] 구명보트

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

프로그래머스

알고리즘 설계

💡idea.

최대한 적은 수의 구명보트를 사용해야 하므로, 가벼운 사람(작은 수)들끼리 최대한 모여 타야 한다고 생각했다. 그러나 최대한 남는 자리가 없도록 하려면 무거운 사람과 가벼운 사람을 적절히 섞어 타야한다. 한 번에 가벼운 경우와 무거운 경우를 모두 고려해야 하므로 투포인터를 사용한다.

 

🎲step.

1. 순서는 고려 대상이 아니므로, 배열을 정렬한다.

2. 가벼운 사람을 위한 인덱스(l), 무거운 사람을 위한 인덱스(h) 변수 두 가지를 한 번에 활용하여 people 배열을 순회한다.

3. 무거운 사람을 기준으로 차례로 보트에 태운다. 이 때 '보트에 태운다.'는 개념은 인덱스를 증감하며 구현할 수 있다.

알고리즘 구현

def solution(people, limit):
    answer = 0
    
    people.sort()

    h = len(people) - 1
    l = 0
    
    while l <= h:
        if people[l] + people[h] <= limit:	# 가벼운 사람이 함께 탈 수 있으면
            l += 1		# 보트에 함께 태운다.
        
        # 무거운 사람은 항상 보트에 탄다.
        answer += 1
        h -= 1
        
    return answer

* 출처: ChatGPT

나다어

• 문제를 꼼꼼히 읽자. '한 번에 최대 2명씩 밖에 탈 수 없다'는 조건을 읽지 않아서, 오름차순 정렬 후 제한 전까지 계속해서 더하는 오답을 생각해냈다.
• 정렬 시 배열.sort 는 배열 자체를 바꾸고, sorted(배열) 은 정렬된 배열을 반환한다.

투 포인터 알고리즘

• 포인터 2개를 준비한다. 시작과 끝을 알 수 있도록 start, end 라고 한다.
• 맨 처음에는 start = end = 0이며, 항상 start<=end을 만족해야 한다.
• 2개의 포인터는 현재 부분 배열의 시작과 끝을 가리키는 역할을 한다.

• 이 알고리즘은 매 루프마다 항상 두 포인터 중 하나는 1씩 증가하고 있고, 각 포인터가 N번 누적 증가해야 알고리즘이 끝난다. 따라서 각각 배열 끝에 다다르는데 O(N)이라서 합쳐도 O(N)이 된다.

Ready-For-Tech-Interview/Algorithm/투포인터 알고리즘.md at master · WooVictory/Ready-For-Tech-Interview