체육복 - level 2

해결방법

좀 더 신중히 고민하면 쉬운문제이다. 여벌 옷은 가지고 온 아이들은 수업에 참여 할 수 있다. 그래서 lost, reserve에서 같은 번호가 있다면 두 곳 모두에서 제거해주는 전처리가 필요하다.

Time Complexity

sort과정이 두번 있다.
$$ O(2NlogN) $$
전처리 과정은 reserve와 lost같은 것을 찾으므로 for문 2개로 돌아간다.
$$ O(2N^{2}) $$
마지막 계산 같다.
$$ O(2N^{2}) $$
따라서
$$ O(2NlogN + 4N^{2}) $$

전체 소스

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(int n, vector<int> lost, vector<int> reserve) {
    sort(lost.begin(), lost.end());
    sort(reserve.begin(), reserve.end());
    for(int i = 0; i < lost.size(); ++i)
        for(int j = 0; j < reserve.size(); ++j)
            if(lost[i] == reserve[j]) {
                reserve.erase(reserve.begin() + j);
                lost.erase(lost.begin() + i);
                i--;
                break;
            }
    int answer = n - lost.size();
    for(int i = 0; i < lost.size(); ++i) {
        for(int j = 0; j < reserve.size(); ++j) {
            if(lost[i] - 1 == reserve[j] || lost[i] + 1 == reserve[j]) {
                answer++;
                reserve.erase(reserve.begin() + j);
                break;
            }
        }
    }
    return answer;
}