체육복 그리디

#include <string>
#include <vector>

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    vector<int> a(n+2,1);
    for(int i=0;i<reserve.size();i++)
    {
        a[reserve[i]]++;
    }
    for(int i=0;i<lost.size();i++)
    {
        a[lost[i]]--;
    }
    for(int i=1;i<=n;i++)
    {
        if(a[i-1]==0 && a[i]==2)
        {
            a[i-1]=1;
            a[i]=1;
        }
        else if(a[i]==2 && a[i+1]==0)
        {
            a[i]=1;
            a[i+1]=1;
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(a[i]>0)
        {
            answer++;
        }
    }
    
    return answer;
}

 

n                                      lost                                  reserve                                  return

5

[2, 4]

[1, 3, 5]

5

 

1.학생수에 2를 더한 크기의 vector를 만든 후 모든 값을 1로 초기화해준다.(비교시 벡터 자료구조 문제를없애기위해)

배열

0 1 2 3 4 5 6

1 1 1 1 1 1 1

 

2.여벌을 가져온 학생번호의 값을 1씩 증가

배열

0 1 2 3 4 5 6

1 2 1 2 1 2 1

 

3.옷을 안가져온 학생번호의 값을 1씩 감소

배열

0 1 2 3 4 5 6

1 2 0 2 0 2 1

 

이 비교를 위해 학생수+2

4.if 앞번호 학생의 옷이 0벌이고 현재번호 학생의 옷이 2벌이면 현재번호 학생의 옷1벌을 앞번호 학생에게 양도

즉 앞번호 옷 갯수:1 현재번호 옷 갯수:1

 

5.if 현재번호 옷의 갯수가 2벌이고 뒷번호 옷의 갯수가 0벌이면 현재번호 학생의 옷1벌을 뒷번호 학생에게 양도

즉 현재번호 옷 갯수:1 뒷번호 옷 갯수:1 

 

6.옷의갯수가 1개 이상인 학생 수 계산

 

set STL 사용법(학생수에 비해 옷을 추가로 들고온수가 현저히 작을때)

#include <vector>
#include <set>
#include <unordered_set>
using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {    
    unordered_set<int> a(lost.begin(),lost.end());//잃어버린학생
    set<int> b;//추가로 들고있는 학생 (교집합x)
    unordered_set<int> c;//교집합 (추가로 들고있고 잃어버린학생)
    for(auto& p:reserve)
    {
        if(a.find(p)==a.end())
        {
            b.insert(p);
        }
        else
        {
            c.insert(p);
        }
    }
    for(auto& q:c)
    {
        a.erase(q);//교집합인 학생을 옷을 잃어버린 학생set에서 삭제
    }
    for(auto& z:b)
    {
        if(a.find(z-1)!=a.end())//추가로 들고있는 학생 - 1 의 값의 학생이 옷을 잃어버린 학생 set에 있다면
        {
            a.erase(z-1);//옷을 잃어버린 학생 set에서 해당 학생 삭제
        }
        else if(a.find(z+1)!=a.end())
        {
            a.erase(z+1);
        }
    }
    return n-a.size();//전체 학생 수 에서 잃어버린학생 set 크기를 빼줌
    
}