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

문제

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

프로그래머스

 

---

코드

def solution(people, limit):
    ans = 0
    left = 0
    right = len(people) - 1
    people.sort()
    
    while left <= right:
        if people[left] + people[right] <= limit:
            ans += 1
            left += 1
            right -= 1
        else: 
            ans += 1
            right -= 1
    return ans

 

---

설명

사실 그리디 알고리즘 인지도 몰랐다ㅠㅠ

그 중에서도 투 포인터 알고리즘을 이용해서 풀이를 했어야 했다.

 

- while문은 조건문이 참인 동안에 while문에 속한 문장들이 반복해서 수행됨! 

 

** 투 포인터 알고리즘

- 두 개의 포인터를 사용하는 탐색 기법

** 

- 각 원소마다 모든 값을 순회해야 할 때, O(N^2)
- 연속하다는 특성을 이용해서 처리, O(N)
- 두 개의 포인터(커서)가 움직이면서 계산

 

<코드 설명>

1. 배열을 오름차순 정렬

2. left, right 포인터 사용

- 양 극단에 있는 값인 최솟값(왼쪽 포인터)과 최댓값(오른쪽 포인터)으로 시작.

- 두 값을 더함 <= limit: 함께 타기 가능. 왼쪽 포인터 +1, 오른쪽 포인터 -1

- 두 값을 더함 > limit: 함께 타기 불가능. 오른쪽 포인터 -1