Programmers: 체육복

문제

• https://programmers.co.kr/learn/courses/30/lessons/42862
• 왜 이 문제에 1시간 반이나 했나...

핵심 내용

• 문제 좀 잘 읽어볼 것
• 도둑이 들었으면 신고가 먼ㅈ..
• 체육복을 잃어버린 사람들을 기준으로
  • '잃어버린 사람'이 체육복을 더 빌릴 수 있는가?
• 를 해결하면 됨
• 체육복을 빌릴 수 있는 기준은, 문제에 나와있는 설명대로 '잃어버린 사람 - 1' 아니면 '잃어버린 사람 + 1' 만 확인하면 됨
• 다만
  • 마지막 제한사항에 '여벌 체육복을 가지고 온 사람도 도난 가능!' 이라고 되어 있음
  • 즉, 여벌 체육복을 도둑맞은사람은 체육복을 빌려주지 못하는 제한이 생김[그러나 본인은 입어서 체육수업 나갈 수 있음]
  • 즉[again?], 이 케이스는 도둑 맞은 사람[lost array]과 빌려줄 수 있는 사람에서 해당 사람들을 제외 해야됨

알고리즘

1. 현재 input 인 Lost/Reserve를 모두 정렬
2. Lost/Reserve가 겹치는 부분[교집합]을 모두 제외한 new_lost , new_reserve 생성
3. new_lost를 순회하면서
   체육복을 빌리지 못하는 경우 n[총 인원 수]을 1씩 감소
4. 최종적으로 n 리턴[들을 수 있는 총 인원 수]

코드

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

using namespace std;

bool contains(vector<int> target_vector, int target) {
    return find(target_vector.begin(), target_vector.end(), target) != target_vector.end();
}

void remove_element(vector<int>& target_vector, int target) {
    for (int i = 0; i < target_vector.size(); i++) {
        if (target_vector[i] == target) {
            target_vector.erase(target_vector.begin() + i);
            return;
        }
    }
}

vector<int> create_new_lost(vector<int>& lost, vector<int>& reserve) {
    vector<int> same_list(lost.size() + reserve.size(), -1);
    set_intersection(lost.begin(), lost.end(), reserve.begin(), reserve.end(), same_list.begin());
    vector<int> new_lost;
    
    for (int i = 0; i < lost.size(); i++) {
        if (!contains(same_list, lost[i])) {
            new_lost.push_back(lost[i]);
        }
    }
    
    return new_lost;
}

vector<int> create_new_reserved(vector<int>& lost, vector<int>& reserve) {
    vector<int> same_list(lost.size() + reserve.size(), -1);
    set_intersection(lost.begin(), lost.end(), reserve.begin(), reserve.end(), same_list.begin());
    vector<int> new_reserved;
    
    for (int i = 0; i < reserve.size(); i++) {
        if (!contains(same_list, reserve[i])) {
            new_reserved.push_back(reserve[i]);
        }
    }
    
    return new_reserved;
}

int solution(int n, vector<int> lost, vector<int> reserve) {
    sort(lost.begin(), lost.end());
    sort(reserve.begin(), reserve.end());
    vector<int> new_lost = create_new_lost(lost, reserve);
    vector<int> new_reserve = create_new_reserved(lost, reserve);

    for (int i = 0; i < new_lost.size(); i++) {
        if (contains(new_reserve, new_lost[i] + 1)) {
            remove_element(new_reserve, new_lost[i] + 1);
            // n--;
            continue;
        }

        if (contains(new_reserve, new_lost[i] - 1)) {
            remove_element(new_reserve, new_lost[i] - 1);
            // n--;
            continue;
        }

        n--;
    }
    return n;
}