체육복 42862

문제

접근 방법

잃어버린 사람에 한해서 주변인에 여벌을 확인하는 방법을 사용하면 될 것 같았다.

코드

하나씩 세어보는 코드

#include <string>
#include <vector>
using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve)
{
    int answer = 0;
    bool res[31] = {
        false,
    },
         los[31] = {
             false,
         };
    for (int i = 0; i < lost.size(); ++i)
    {
        los[lost[i]] = true;
    }
    for (int i = 0; i < reserve.size(); ++i)
    {
        if (los[reserve[i]])
            los[reserve[i]] = false;
        else
            res[reserve[i]] = true;
    }
    for (int i = 1; i <= n; ++i)
    {
        if (los[i])
        {
            if (res[i - 1])
            {
                res[i - 1] = false;
                ++answer;
            }
            else if (res[i + 1])
            {
                res[i + 1] = false;
                ++answer;
            }
        }
        else
        {
            ++answer;
        }
    }
    return answer;
}

잃어버린 위치만 확인하는 코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve)
{
    sort(lost.begin(), lost.end());
    int answer = n;
    bool res[31] = {
        false,
    },
         los[31] = {
             false,
         };
    for (int i = 0; i < lost.size(); ++i)
    {
        los[lost[i]] = true;
    }
    for (int i = 0; i < reserve.size(); ++i)
    {
        if (los[reserve[i]])
            los[reserve[i]] = false;
        else
            res[reserve[i]] = true;
    }
    for (int i = 0; i < lost.size(); ++i)
    {
        int j = lost[i];
        if (los[j])
        {
            if (res[j - 1])
            {
                res[j - 1] = false;
            }
            else if (res[j + 1])
            {
                res[j + 1] = false;
            }
            else
            {
                --answer;
            }
        }
    }
    return answer;
}

풀이

하나씩 확인해보며 학생 수를 증가시키거나 전체 학생 수에서 잃어버린 사람을 빼주는 2가지 방법으로 가능하다.
후자의 경우 lost를 정렬해주지 않으면 최댓값이 되지 못한다. (5, 3의 순서로 lost가 적혀있으면 4, 6의 여벌 옷이 있더라도 5번이 먼저 4를 가져가서 3은 4의 여벌 옷을 못 가져갈 수 있다.)

잃어버렸지만, 여벌 옷이 있는 경우도 생각해둬야 한다.