체육복 (프로그래머스)

부분 단계적으로 해결하는 그리디 알고리즘 문제였다.

 

여벌 체육복을 가져온 학생이 도난 당할 수 있다는 점에 주목하자. 이 경우에는 여벌 체육복을 가져왔다고 해도 다른 학생에게 체육복을 빌려줄 수 없다.

 

접근 방법은 다음과 같다.

1. 도난 당한 학생을 담은 벡터에서 여벌 체육복을 가져온 학생들을 뺀다. (도난 당했지만 체육 수업을 들을 수 있으므로)

2. 마찬가지로 잃어버린 학생을 담은 벡터에서 위 학생을 뺀다.

3. 남은 잃어버린 학생들은 체육 수업을 들을 수 없으므로, 이 학생들 앞뒤로 여벌의 체육복이 있는 학생이 존재하는지 검사한다.

4. 만약 있다면 여벌을 가진 학생은 이제 체육복을 빌려줬으므로 벡터에서 빼준다.

5. 답은 (학생 수) - (잃어버린 학생 수) + (잃어버렸지만 여벌이 있는 학생 수) + (빌려준 수) 가 된다.

 

코드는 다음과 같다.

#include <string>
#include <vector>

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    
    answer = n - lost.size();
   
    for(auto iter_lost = lost.begin(); iter_lost != lost.end();)
    {
        bool checkErase = false;
        for(auto iter_reserve = reserve.begin(); iter_reserve != reserve.end();)
        {
            // 여벌이 있지만 잃어버렸으므로 원소를 빼준다.
            if((*iter_lost) == (*iter_reserve))
            {
                iter_reserve = reserve.erase(iter_reserve);
                checkErase = true;
                ++answer;
                break;
            }
             ++iter_reserve;
        }
        // 마찬가지로 잃어버렸지만 여벌이 있으므로 원소를 빼준다.
        if(checkErase)
            iter_lost = lost.erase(iter_lost);
        else
            ++iter_lost;
    }
    
    // 잃어버려서 체육수업을 들을 수 없는 학생들중
    for(const auto student_lost : lost)
    {
        for(auto iter_reserve = reserve.begin(); iter_reserve != reserve.end();)
        {
            // 앞, 뒤로 빌려줄 학생이 있으므로 빌려준다.
            if(student_lost - 1 == (*iter_reserve) || student_lost + 1 == (*iter_reserve))
            {
                iter_reserve = reserve.erase(iter_reserve);
                ++answer;
                break;
            }
            ++iter_reserve;
        }
    }
    
    return answer;
}