Level 1. 체육복

Level 1. 체육복

 

 

굉장히 난잡하게 풀었다.

 

입출력 예시가 오름차순으로 되어 있어서 정렬된 상태로 주어지는 줄 알았는데 아닌 경우도 있어서 정렬을 해야했다.

 

탐욕법을 하되 작은 수부터 처리해야 하기 때문이다.

 

첫 번째 for문은 여벌을 가진 학생 중 도난당한 학생을 제거하는 부분이다.

 

번호가 작은 학생부터 앞번호, 뒷번호 차이가 ±1 인 경우를 세어 해결했다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve)
{
    int nLost;
    vector<int> t_lost;

    sort(lost.begin(), lost.end());
    sort(reserve.begin(), reserve.end());

    t_lost = lost;

    for (int l : t_lost)
    {
        auto it = find(reserve.begin(), reserve.end(), l);
        auto jt = find(lost.begin(), lost.end(), l);

        if (it != reserve.end())
        {
            reserve.erase(it);
            lost.erase(jt);
        }
    }

    nLost = lost.size();

    for (int l : lost)
    {
        auto it = find(reserve.begin(), reserve.end(), l - 1);
        auto jt = find(reserve.begin(), reserve.end(), l + 1);

        if (it != reserve.end())
        {
            --nLost;
            reserve.erase(it);
        }
        else if (jt != reserve.end())
        {
            --nLost;
            reserve.erase(jt);
        }
    }

    return n - nLost;
}

 

문제를 풀면서 무슨 이런 문제가 있나 싶었는데 다른 사람의 풀이를 보니 배울 게 있었다.

 

두 상태(잃어버림, 여벌 가짐)를 가지는 경우 bitset을 사용할 수 있다.

 

특히, 이번 경우처럼 두 상태가 상쇄(여벌을 가진 학생이 도난당함)되는 경우에는 int 배열을 만들어 [-1, 0, 1]로 상태를 표현할 수 있다.

 

이 풀이에서도 체육복을 빌릴 때는 앞번호 학생부터 확인해야 한다.

 

lost: [2,4], reserve: [1, 3] 상황에서 1 ->2, 3->4에게 빌려주면 모두 수업을 들을 수 있지만, 3->2에게 빌려주면 4가 수업을 듣지 못하게 된다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve)
{
    int student[31] = {0};

    for (int l : lost)
        --student[l];

    for (int r : reserve)
        ++student[r];

    for (int i = 1; i <= n; ++i)
    {
        if (student[i] == -1)
        {
            if (student[i - 1] == 1)
                student[i - 1] = student[i] = 0;
            else if (student[i + 1] == 1)
                student[i] = student[i + 1] = 0;
        }
    }

    return n - count(student + 1, student + n + 1, -1);
}