코딩테스트 연습->탐욕법(Greedy)->체육복

출처입니다 : https://programmers.co.kr/learn/courses/30/lessons/42862

코딩테스트 연습 - 체육복

동영상 강의를 보고,, 이해는 제대로 하지 못하고 외워서 작성 한거 같습니다 -_-;;;;;;

계속 동영상 강의를 다시 보고 이해해보도록 노력 해보려 합니다 -_;;;

#include <vector>
#include <algorithm>

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    //int answer = 0;
    
    // 앞뒤에 벽을 만들고 , 전수 1로 초기화 진행 
    vector<int> d(n+2 , 1);
    
    // 체육복 여벌이 있는 번호에 대하여 +1 을 처리 한다.
    for(int i = 0 ; i < reserve.size() ; i++) 
        d[reserve[i]]++;
    
    // 체육복 잃어버린 번호에 대하여 -1을 처리 한다.
    for(int i = 0 ; i < lost.size() ; i++) 
        d[lost[i]]--;
    
    // 여벌이 있는 번호에 대하여 자신의 앞뒤 번호가 0 인 요소에 1을 할당 해주도록 한다.
    // 앞뒤에 방벽을 만들었으므로 1부터 시작 
    for(int i = 1 ; i <= d.size() ; i++) {
        if(d[i] == 2 && d[i-1] == 0)
            d[i] = d[i-1] = 1;
        else if(d[i] == 2 && d[i+1] == 0)
            d[i] = d[i+1] = 1;
    }
    
    // 0 인것을 전체 카운트에서 제외 하여 리턴 처리 한다.
    return n - count(d.begin() , d.end() , 0);
}

 

/////////////////////////////////////////////////////////////////////////////////

2021.09.16 일 추가 , set 과 unordered_set을 이용

 

#include <vector>
#include <algorithm>

#include <unordered_set>
#include <set>

#include <iostream>

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
   int answer = 0 ; 
   
    // reserve를 담는다 . 
    set<int> r(reserve.begin() , reserve.end());
    
    //lost를 담는다.
    unordered_set<int> l;
    for(int i = 0 ; i < lost.size() ; i++)
        l.insert(lost[i]);
    
    //reserve에서 lost와 일치하는 부분을 삭제 진행 
    for(auto& i : l)  {
        if(r.find(i) != r.end()) {
            r.erase(i);
            l.erase(i);
        }
    }
    
    
    // reserve 의 앞뒤를 검색 한다.
    for(auto& i : r) {
        
        if(l.find(i-1) != l.end()) {
            l.erase(i-1);    
        }
        else if(l.find(i+1) != l.end()) {
            l.erase(i+1);
        }
        
    
    }

    
   return n - l.size();
}