#42862 체육복

문제 정리

바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있
최대한 많은 학생이 체육수업을 들어야 함

lost == reserve인 경우에는 여벌을 써야해서 못 빌려줌

생각해보기

pop쓰려면 뒤에서 하는게 편할 듯?
lost를 뒤에부터 돌면서 좌우로 reserve가 있으면
그 reserve랑 lost를 pop..이 아니라 pop이 안될수도 있으니까
앞 뒤는 상관없구나 어차피 at idx 값을 지워줘야 하는거구나…

암튼 다 지우고 나서 lost의 size를 n에서 빼면 되는데
lost == reserve인 경우에는 어떻게 검사하지? 미리 처음에 돌면서 지워놔야하나..는 비효율적인데 너무
어차피 앞뒤만 빌려줄 수 있으니까 at idx 값 지우기 전에 같은지 검사하면 될듯?

코드 쓰기

v.erase(v.begin() + index); // 특정 인덱스의 원소 삭제

내 풀이

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

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    
    int sameIdx = 0;
    int tempIdx = 0;
    int lostIdx = 0;
    
    sort(lost.begin(), lost.end());
    sort(reserve.begin(), reserve.end());
    
    for(int i=lostIdx; i<lost.size(); i++){
        
        for(int k= sameIdx; k<reserve.size(); k++){
            // 여벌 = 도난당한 학생인지 검사
            if (reserve[k] == lost[i]){
                cout << reserve[k] << "same with" << lost[i] << endl;
                lost.erase(lost.begin() + i);
                reserve.erase(reserve.begin() + k);
                sameIdx = k;
                lostIdx = i;
                cout << lostIdx << "is lost" << endl;
            }
        }
        
        for(int k=tempIdx; k<reserve.size(); k++){
            if(reserve[i] == (lost[i]-1) || reserve[i] == (lost[i]+1)){
                lost.erase(lost.begin() + i);
                reserve.erase(reserve.begin() + k);
                tempIdx = k;
                lostIdx = i;
            }
        }
    }
    
    answer = n - lost.size();
    
    return answer;
}

이 풀이의 문제점 : erase 하고 나서 인덱스 변화를 고려하지 않았음… 다 지우고 다시 짜봤다

    
    for(int i=0; i<lost.size(); i++){
        for(int k=0; k<reserve.size(); k++){
            if(abs(lost[i]-reserve[k]) == 1){ // 차이가 1이면
                lost.erase(lost.begin() + i);
                reserve.erase(reserve.begin() + k);
                i--;
                k--;
                break;
            } else {
                break;
            }
        }
    }

for 문을 쓰니까 자꾸 인덱스때문에 머리아픔;

      // 빌려줄 수 있나 보기
    
    for(int i=0; i<lost.size(); i++){
        for(int k=0; k<reserve.size(); k++){
            
            if(abs(lost[i]-reserve[k]) == 1){
                lost[i] = -6;
                reserve[i] = -6;
                break;
            }
            
        }
    }
    
    int left = 0;
    for (int i=0; i<lost.size(); i++){
        if(lost[i] != -6){
            left++;
        }
    }
    
    answer = n - left;

이렇게 했는데 테케 2,4 번만 통과 못 했다. 전에꺼는 2, 4는 붙고 다른 게 틀렸었는데…
결국 구글링 해서 새로 얻은 인사이트대로 다시 짰다 ㅠ___ ㅠ 짜증

#include <string>
#include <vector>

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0; 

    vector<int> students(n+2, 0);

    // 도둑맞았지만 여분있는 애들 처리
    for(int i: lost){
        students[i]--;
    }

    for(int i: reserve){
        students[i]++;
    }

    // 빌려주기 처리
    for(int i=1; i<students.size()-1; i++){
        if(students[i] == -1){
            if(students[i-1] == 1){
                students[i]++;
                students[i-1]--;
            }else if (students[i+1] == 1){
                students[i]++;
                students[i+1]--;
            }
        }
    }

    for(int i=1; i<=n; i++){
        if(students[i] >= 0){
            answer++;
        }
    }

    return answer;
}

에휴ㅜ

풀고 나서 알게된 것

lost, reserve가 오름차순 정렬 되어 있다는 보장이 없었다..!!

students 벡터를 선언해서 -1, 0, 1 해주니까 얼마나 편해..~ㅜㅜㅜ