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

문제

---

문제를 보시려면 링크를 클릭해주세요.

풀이

---

탐욕법(그리디 알고리즘)을 이용하여 풀 수 있습니다.

1. 체육복을 도난당한 학생은 -1, 여벌을 가지고 있는 학생은 +1을 해서 student 배열을 만들어줍니다.

2. 도난당한 학생의 앞, 뒤 학생에게 여벌 체육복이 있는지 확인하는데, 이 때 앞 번호 학생이 우선적으로 빌려주게됩니다.
3. 체육복을 빌려줬다면 그 학생도 -1 해줍니다.
4. 결론적으로 도난당했으면 -1, 자신의 체육복이 있으면 0, 여벌까지 있으면 1값을 가지고 있습니다.
5. 0이상의 값을 가진 학생이 체육수업을 들을 수 있는 학생입니다.

1번 학생의 앞 번호, n번 학생의 뒷 번호는 없지만 편의상 0으로 채워줌

student 배열 크기: n+2

소스 코드

---

#include <vector>

using namespace std;

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