프로그래머스) Lv1 - 체육복

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

코딩테스트 연습 - 체육복

탐욕법으로 풀이하는 문제입니다.

 

- 모든 학생이 체육복을 하나씩 가지고 있다고 가정한 리스트를 만듭니다.

- lost vector를 돌면서 해당 학생의 체육복수를 감소, reserve vector를 돌면서 증가시킵니다.

- list vector를 돌면서 체육복이 없는 학생이 앞/뒤의 학생이 여분 체육복을 가지고 있다면 빌려옵니다.

---

C++ 소스 코드

#include <string>
#include <vector>

using namespace std;

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