[Programmers_C++]#Level2_구명보트, 투 포인터 알고리즘

 

#1. 문제

 

 

---

 

#2. 풀이

 

1. 투 포인터 알고리즘

[알고리즘]#7_투 포인터

 

• • [정의] : '투 포인터' 알고리즘은 두 개의 포인터를 활용해 원하는 조건을 만족하는 부분을 찾는 알고리즘입니다.
  • [특징] : '투 포인터' 알고리즘은 일반적으로 정렬된 배열 혹은 리스트에서 활용합니다.
  • [동작 방식] 
    1. 배열의 시작 지점을 가리키는 포인터, 그리고 끝 지점을 가리키는 포인터, 두 개의 포인터를 초기화합니다.
    2. 두 포인터가 움직이며 주어진 조건을 만족하는지 검사합니다.
    3. 조건을 만족할 경우, 원하는 동작을 수행하고, 조건을 만족하지 못할 경우, 포인터를 이동시킵니다.
    4. 원하는 결과 값을 얻을 때까지, 2~3번 동작을 반복합니다.

 

2. 두 명 타서 가벼우면 투 포인터 알고리즘 일찍 끝내기!

1. 먼저, 사람들의 몸무게 목록을 오름차순 정렬해줍니다.
2. left 포인터는 people 목록의 시작 지점으로, 그리고 right 포인터는 people 목록의 마지막 지점으로 초기화합니다.
3. left 포인터가 가리키는 사람의 몸무게와 right 포인터가 가리키는 사람의 몸무게를 더해 limit와 비교합니다.
4. 몸무게의 합이 limit 보다 작거나 같을 경우, 각각 left 포인터는 오른쪽, right 포인터는 왼쪽으로 한 칸 이동합니다.
5. 몸무게의 합이 limit 보다 클 경우, right 포인터만 왼쪽으로 한 칸 이동합니다.
6. 그리고, 보트 한 개를 추가합니다.
7. 현재 가장 가벼운 사람과 가장 무거운 사람의 몸무게 합이 limit과 같거나 적을 경우, 투 포인터 알고리즘이 일찍 종료.

 

---

 

#3. 코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;
    
    // 오름차순 정렬
    sort(begin(people), end(people));
    
    // 투 포인터
    int left = 0;
    int right = people.size()-1;
    
    while(left <= right)
    {
        // 남아 있는 인원 중 가장 가벼운 인원과 가장 무거운 인원이 1개의 구명보트에 함께 탈수 있는지 체크합니다.
        if(people[left] + people[right] <= limit)
        {
            // #1.  2명이 1개의 보트에 함께 탈 수 있다면, left 포인터를 오른쪽으로 한 칸 이동합니다.
            //      즉, left+1 과 right-1 되며, 해당 루프가 일찍 끝나게 되어 answer++가 더 적게 수행되어,
            //      최종적으로 최소 보트 개수를 찾을 수 있습니다.
            left++;
        }
        // #2. right 포인터를 왼쪽으로 한 칸 이동시킵니다.
        right--;
        answer++;
    }
    
    return answer;
}

 

---