[프로그래머스/C++] 체육복 : Greedy

문제

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

풀이

⭐정보를 배열 하나에 정리한다.

1로 초기화
여분 가져온 학생: +1 / 도난 당한 학생: -1

그럼 총 3가지의 경우가 생김
0: 도난 당해서 체육복 X
1: 여분X and 도난X, 여분O and 도난O
2: 도난 당하지 않고, 여분의 체육복 있어서 빌려줄 수 있음

따라서 i=0 부터 i=n 까지 반복문을 돌면서 i가 0일 때 앞 뒤 중에 2인 학생이 빌려주는 작업을 수행한다.

코드

#include <vector>

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    vector<int> student(n,1);
    
    for(int i=0; i<reserve.size(); i++) {
        student[reserve[i] - 1]++;
    }
    for(int i=0; i<lost.size(); i++) {
        student[lost[i] - 1]--;
    }
    
    for(int i=0; i<n; i++) {
        if(i>0 && student[i]==0 && student[i-1]==2) { //첫번째 사람은 빌릴 수 없음
            student[i]++;
            student[i-1]--;
        }
        if(i<n-1 && student[i]==0 && student[i+1]==2) { //마지막 사람은 빌릴 수 없음
            student[i]++;
            student[i+1]--;
        }
    }
    
    
    for(int s:student) {
        if(s > 0) {
            answer++;
        }
    }
    
    return answer;
}