[프로그래머스] 체육복

 

1. 문제

 

전체 학생의 수 n,

체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 

여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때,

 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

 

2. 코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;

//n : 전체 학생의 수
//lost : 체육복을 도난당한 학생들의 번호 배열
//reserve : 여벌의 체육복을 가져온 학생들의 번호 배열
int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    
    //앞 뒤 수를 비교할 것이기 때문에 정렬 과정이 꼭 필요함
    sort(lost.begin(),lost.end());
    sort(reserve.begin(),reserve.end());
    
    //두가지 배열을 통해 벡터의 삽입,삭제를 진행하지 않고
    //체크를 했는지 표시해줌
    bool isChecked[31]={false};
    bool isCheckedReserve[31]={false};
    int coverNum=0;
    
    //먼저 같은 값들은 모두 true로 변경하고 빌려줌으로써 메꿀수 있는 사람수를 증가
    for(int i=0;i<reserve.size();i++)
    {
        for(int j=0;j<lost.size();j++){
            if(reserve[i]==lost[j]){
                isChecked[j]=true;
                isCheckedReserve[i]=true;
                coverNum++;
            }
        }
    }
    //그 후 남은 것들을 이용하여 앞뒤의 경우의 수를 통해 메꿀수 있는 학생 수 계산
    for(int i=0;i<reserve.size();i++){
        if(coverNum==lost.size())break;
        for(int j=0;j<lost.size();j++){
            if(isChecked[j]||isCheckedReserve[i]) continue;
            else if(lost[j]-1==reserve[i]||lost[j]+1==reserve[i])
            {
                coverNum++;
                isChecked[j]=true;
                isCheckedReserve[i]=true;
            }
        }
    }
    
    //정답 = 총학생수 - 잃어버린 체육복 수 + 메꾼 학생 수
    answer = n-lost.size()+coverNum;
    
    return answer;
}

 

3. 해설

//n : 전체 학생의 수
//lost : 체육복을 도난당한 학생들의 번호 배열
//reserve : 여벌의 체육복을 가져온 학생들의 번호 배열
int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    
    //앞 뒤 수를 비교할 것이기 때문에 정렬 과정이 꼭 필요함
    sort(lost.begin(),lost.end());
    sort(reserve.begin(),reserve.end());

먼저 경우의 수에서 예외 사항을 제외하기 위해 정렬을 진행해준다. 잃어버린 사람들과 여벌의 체육복을 가지고 있는 사람들의 배열을 정렬을 진행한다.

    //두가지 배열을 통해 벡터의 삽입,삭제를 진행하지 않고
    //체크를 했는지 표시해줌
    bool isChecked[31]={false};
    bool isCheckedReserve[31]={false};
    int coverNum=0;
    
    //먼저 같은 값들은 모두 true로 변경하고 빌려줌으로써 메꿀수 있는 사람수를 증가
    for(int i=0;i<reserve.size();i++)
    {
        for(int j=0;j<lost.size();j++){
            if(reserve[i]==lost[j]){
                isChecked[j]=true;
                isCheckedReserve[i]=true;
                coverNum++;
            }
        }
    }

각각 체크를 했는지 안했는지 기록할 배열 두개를 준비한다. 만약 여벌을 이미 빌려주고, 대여 받은 사람의 경우 체크할 필요가 없기 때문이다.

맨 처음 여벌을 준비한 학생이 잃어버렸을 경우를 체크해준다. (reserve[i]==lost[j]) 이 경우

    //그 후 남은 것들을 이용하여 앞뒤의 경우의 수를 통해 메꿀수 있는 학생 수 계산
    for(int i=0;i<reserve.size();i++){
        if(coverNum==lost.size())break;
        for(int j=0;j<lost.size();j++){
            if(isChecked[j]||isCheckedReserve[i]) continue;
            else if(lost[j]-1==reserve[i]||lost[j]+1==reserve[i])
            {
                coverNum++;
                isChecked[j]=true;
                isCheckedReserve[i]=true;
            }
        }
    }
    
    //정답 = 총학생수 - 잃어버린 체육복 수 + 메꾼 학생 수
    answer = n-lost.size()+coverNum;
    
    return answer;
}

그 후 체크하지 않은 값들을 다시 체크해준다. 이 경우 여벌을 가지고 있는 학생의 id번호 앞뒤인지 아닌지를 체크해주면서 만약 여벌을 빌려주면 coverNum의 값을 높여준다. 이때 coverNum은 말그대로 얼만큼 잃어버린 학생들의 공백을 메꿀수 있는지 나타내는 변수이다.

따라서 정답은 총학생수에 잃어버린 체육복 수를 빼고 메꾼 학생 수를 더해주면 된다.