[C++] 프로그래머스 코딩테스 연습_탐욕법_체육복

최종코드:

#include <string>
#include <vector>
#include <set>
#include <algorithm>    // set_difference

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    // 중복 제거, 정렬, 탐색 속도 향상을 위해 set으로 변경
    set<int> s_lost(lost.begin(), lost.end());
    set<int> s_reserve(reserve.begin(), reserve.end());
    
    // 각 set에서 중복 제거
    for (auto it=s_reserve.begin(); it!=s_reserve.end(); ) {
        if (s_lost.count(*it)) {
            s_lost.erase(*it);
            it = s_reserve.erase(it);
        }
        else
            ++it;
    }
    
    vector<bool> ablePE(n+2, true);
    for (int i : s_lost)
        ablePE[i] = false;
    
    // 양도 가능한 체육복 수만큼 answer증가
    int answer = n-s_lost.size();
    for (int i : s_reserve) {
        if (ablePE[i-1] == false) {
            ablePE[i-1] = true;
            answer++;
            continue;
        }
        else if (ablePE[i+1] == false) {
            ablePE[i+1] = true;
            answer++;
        }
    }
        
    return answer;
}

---

교집합을 빼기 위해 set의 차집합을 이용하려했으나, 생각보다 코드가 안이쁜 관계로 직접 반복자를 이용해 빼줬다.

그리디답게 reverse를 돌면서 채울 수 있으면 채웠다. 상식적으로 작은 숫자부터 채워야 최대로 채울 수 있을 것 같으니 말이다.