(C++) - 프로그래머스(고득점 kit - Greedy) : 체육복

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

코딩테스트 연습 - 체육복

greedy문제였습니다.

풀이방법

 1. 학생별 체육복 보유 여부를 판별하기 위한 vector선언

 2. 체육복을 잃어버린 학생들은 해당 vector의 index를 0으로 만들어줍니다.

 3. 그 후 체육복 여분을 가지고 학생의 index를 1씩 증가시켜줍니다.

 4. n까지 학생들을 loop를 돌며 확인합니다.

    만약 i번째 학생이 체육복이 없다면 

    양 옆 여분이 있는 학생(체육복 보유개수 2)을 확인 한 뒤 i번째 학생에게 체육복을 빌려줍니다.

    만약 i-1번째 학생의 체육복 보유 개수가 2개라면 i-1, i번째 학생의 체육복 보유현황은 1입니다.

    만약 i+1번째 학생의 체육복 보유 개수가 2개라면 i+1, i번째 학생의 체육복 보유현황은 1입니다.

 5. 갱신이 완료된 vector를 돌며 체육복 개수가 양수라면 ansewr++해준 후 반환합니다.

 

 

Code

#include <bits/stdc++.h>

using namespace std;

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

int main(){
    vector <int> lost = {1,2,3,5};
    vector <int> reserve = {2,4};
    cout << solution(5,lost,reserve);
}

 

Test Case

n = 4
lost = [2]
reserve = [3]
답 : 4