(프로그래머스 c++)체육복

<문제 설명>
점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다.
다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다.
학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 
예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 
체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

탐욕 법(Greedy)을 쓰는 알고리즘이다.

우선 for문에서 체육복 여분을 가지고 있는 학생들 중 잃어버린 학생이 있는지 확인을 한다.

즉, 자신이 여분을 가지고 있지만 잃어버린 경우를 확인하는 부분이다.

이럴 경우가 있다면 asnwer++을 해주고 해당하는 번호를 lost와 reserve 배열에서 제거.

 

그 후 while문에서 바로 앞 번호 또는 뒷 번호 학생에게 체육복을 빌려줄 수 있는지 확인을 한다.

마찬가지로 이 경우가 있다면 answer++, 해당하는 번호를 lost와 reserve 배열에서 제거를 한다.

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

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    vector<int>::iterator itr;
    answer = n - lost.size();
    
    sort(lost.begin(), lost.end());
    sort(reserve.begin(), reserve.end());
    
    for(int i = reserve.size() - 1; i >= 0; i--)
    {
        if((itr = find(lost.begin(),lost.end(), reserve[i])) != lost.end())
        {
            answer++;
            lost.erase(itr);
            reserve.erase(find(reserve.begin(), reserve.end(), reserve[i]));
        }
    }
    
    while(!lost.empty() && !reserve.empty())
    {
        if((itr = find(reserve.begin(), reserve.end(), lost.front() - 1)) != reserve.end() ||
          (itr = find(reserve.begin(), reserve.end(), lost.front() + 1)) != reserve.end())
        {
            answer++;
            reserve.erase(itr);
        }
        lost.erase(lost.begin());
    }
    
    return answer;
}

탐욕 법을 쓰는 알고리즘인데...

어떻게 쓰는지는 아직 잘 이해가 가지 않는다...

추후에 다시 풀어봐야 하는 문제