코딩테스트 : 체육복

체육복을 도난당한 학생들에게 여벌 체육복을 가진 학생이 앞뒤 번호에 한해 빌려줄 수 있을 때, 수업을 들을 수 있는 학생 수의 최댓값을 구하는 문제이다.

 

문제 핵심

여벌이 있는 학생이 도난당한 경우엔 자기가 입어야 하므로 빌려줄 수 없다.

이들을 먼저 처리해서 lost와 reserve에서 제외해야 한다.

남은 lost에 대해 앞뒤 학생이 여벌을 가지고 있으면 빌려준다.

끝까지 못 빌린 사람 수만큼 전체 학생 수에서 차감.

 

sort에 대한 자세한 설명은 아래 링크에 정리해뒀다.

Sort(정렬)

#include <string>      // string 사용
#include <vector>      // vector 사용
#include <algorithm>   // sort, find, erase 등 사용

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = n;  // 일단 모든 학생이 체육복을 입었다고 가정

    // 정렬을 통해 순서대로 처리 가능하게 정리
    sort(lost.begin(), lost.end());
    sort(reserve.begin(), reserve.end());

    // 여벌이 있지만 도난당한 경우 본인이 입어야 하므로 제외
    for (int& i : lost)
    {
        auto it = find(reserve.begin(), reserve.end(), i); // reserve에서 자기 자신 찾기
        if (it != reserve.end()) // 찾았으면
        {
            reserve.erase(it); // reserve에서 제거
            i = 0; // 이 사람은 더 이상 lost 아님
        }
    }

    // 빌릴 수 있는 경우 처리
    for (int& i : lost)
    {
        if (i == 0) continue; // 이미 처리된 사람은 스킵

        // 앞번호에게 빌릴 수 있는지 확인
        auto it = find(reserve.begin(), reserve.end(), i - 1);
        if (it == reserve.end()) // 없으면
        {
            // 뒷번호에게 빌릴 수 있는지 확인
            it = find(reserve.begin(), reserve.end(), i + 1);
            if (it == reserve.end()) // 없으면 패스
            {
                continue;
            }
        }

        // 빌릴 수 있으면 reserve에서 제거하고 lost에서도 제거
        reserve.erase(it);
        i = 0;
    }

    // 아직 체육복을 못 받은 사람 수 만큼 차감
    for (int i : lost)
    {
        if (i != 0)
            answer--;
    }

    return answer;
}