체육복 C++

 

문제설명

입출력 예

n                             lost                                                         reserve                                                                return

5	[2, 4]	[1, 3, 5]	5
5	[2, 4]	[3]	4
3	[3]	[1]	2

입출력 예 설명

예제 #1
1번 학생이 2번 학생에게 체육복을 빌려주고, 3번 학생이나 5번 학생이 4번 학생에게 체육복을 빌려주면 학생 5명이 체육수업을 들을 수 있습니다.

예제 #2
3번 학생이 2번 학생이나 4번 학생에게 체육복을 빌려주면 학생 4명이 체육수업을 들을 수 있습니다.

 

#include <string>
#include <vector>
#include <algorithm>
#include <string.h>
#include <iostream>


using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer=0;
    
    bool lostArr[31]={false};
    bool reservArr[31]={false};
   
    for(auto i : lost)
    {
        lostArr[i]=true;
    }
        for(auto i : reserve)
    {
        reservArr[i]=true;
        if(lostArr[i])
        {
            lostArr[i]=false;
            reservArr[i]=false;
        }
    }
    
    for(int i=1;i<n+1; i++)
    {
        if(lostArr[i])//해당하는 학생이 가져오지 않았으면 
        {
            if(reservArr[i-1])
            {
                lostArr[i]=false;
                reservArr[i-1]=false;
                answer++;
            }
            else if(reservArr[i+1])
            {
                lostArr[i]=false;
                reservArr[i+1]=false;
                answer++;
            }
        }
        else answer++;
    }
    return answer;
}

 

=> greedy algorithm에 속한 문제라고 하는데 해당 알고리즘이 greedy에 속하는 방법인지는 모르겠습니다. 

=> 주어진 제한사항이 30명이므로 31개 크기의 BOOL형 배열 2개를 선언하였습니다.

 bool lostArr[31]={false}; //true인 경우, 체육복을 안가져온 학생
 bool reservArr[31]={false}; //true인 경우, 체육복을 여분으로 가져온 학생

=> 해당 배열을 초기화를 안 해주어 의도와 달리 값이 들어가는 경우가 있었습니다. 주의해야 합니다. 

=> 순서대로 각 값을 배열에 넣어주며 두 배열에 동일하게 TRUE 값이 들어가 있는 경우, 두 배열의 해당 INDEX값을 FALSE로 변경하였습니다.

=> 이후, lostArr에 있는 값이 True인 경우(학생이 여벌의 옷도 없고, 체육복도 안 가져온 경우) , 본인 앞뒤에 여벌의 체육복을 가지고 있는 학생을 찾고 있을 경우 해당 lostArr의 값과 reservArr의 값도 FALSE로 변환하였습니다.

=> lostArr에 애초에 체육복을 가져온 학생의 경우 answer++을 해주었고, 가져오지는 않았지만 다른 학생에게 빌려올 수 있는 경우도 answer++를 해주어 원하는 값을 반환하였습니다.