탐욕법

 탐욕법 

- 각 순간에 최선의 경우를 택하는 방식 

 

단 순간의 최선이 결국 최대의 최선이 만족될때에만 실행 

 

https://programmers.co.kr/learn/courses/30/lessons/42862

코딩테스트 연습 - 체육복

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

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    int count = 0;
    vector<int> pure_lost;
    
    for(auto it = lost.begin();it != lost.end(); it++)
    {
        auto it_s = find(reserve.begin(),reserve.end(),(*it));
        if(it_s == reserve.end()) 
        {
            pure_lost.emplace_back(*it);
        }
        else
        {
            reserve.erase(it_s);
        }
       
    }
     /*  
    for(auto it = pure_lost.begin();it != pure_lost.end(); it++)
    {
        cout << *it << endl;
    }
    */
    
    for(auto it = pure_lost.begin();it != pure_lost.end(); it++)
    {
        auto it_l = find(reserve.begin(),reserve.end(),(*it)-1);
        auto it_r = find(reserve.begin(),reserve.end(),(*it)+1);

        if(it_l != reserve.end()) // 왼쪽에 빌릴수 있나 ?
        {
            cout << "it_l "<< *it << ',' << *it_l <<endl;
            count++;
            reserve.erase(it_l);
            
        }
        else if(it_r != reserve.end()) // 오른쪽에 빌릴수 있나 ?
        {
            cout << "it_r "<< *it << ',' << *it_r <<endl;
            count++;
            reserve.erase(it_r);
        }
       
    }
    
    for(auto it = reserve.begin();it != reserve.end(); it++)
    {
        cout << *it << endl;
    }
    answer = n - pure_lost.size() + count;
    return answer;
}