[프로그래머스] 체육복 | C++

그리디

- 조건을 따져가며, 특정 번호의 학생에게서 체육복을 빌릴 수있는지확인해가며 품

 

0. 따로 빌려줄 수 있는 학생번호 저장할 배열 생성 -> reserve에 속한 학생을 인덱스로 표시하고 값을 1로 만들어줌

1. lost중에 reserve에도 속해있는 학생을 erase함.

2. lost, reserve 오름차순 정렬(이거 안해서 테케 13,14인가를 틀리던..)

3. lost 개수만큼 반복돌며 reserve[lost[i]-1]==1인지,   reserve[lost[i]+1]==1인지 확인. 빌리고 나서는 해당 reserve 인덱스 값을 0으로 변경.(이제 얘한테는 빌릴 수 없다.)

 

오름차순 정렬한 이유도 3번처럼 무조건 왼쪽부터 확인해서 체육복 빌렸을때, 서로 겹치는 경우가 없게 하려구. 

 

레벨 1에서 이렇게 헤맬일인지 .. 

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
                
int reservePossible[31]; //빌려줄 수 있는 학생 번호

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    int resNum = reserve.size();
    
    for(int i =0;i<resNum;i++){
        reservePossible[reserve[i]] = 1; // 빌려줄 수 있는 놈들 표시
    }
    
    for(auto iter =lost.begin(); iter!=lost.end();){ //빌려줄 수 있었는데 lost한 경우 빼기 
        if(reservePossible[*iter] == 1){
            reservePossible[*iter] = 0;
            iter = lost.erase(iter);
        }else{
            iter++;
        }
    }
    
    int lostNum =lost.size();
    sort(lost.begin(),lost.end());
    sort(reserve.begin(),reserve.end());

    for(int i =0;i<lostNum;i++){ //잃어버린 학생들 반복문 돌면서 누구에게 빌릴 수 있는지..
        
        if(lost[i]>1&&reservePossible[lost[i]-1] == 1){
            //내 왼쪽 친구에게 빌릴 수 있는 경우
            reservePossible[lost[i]-1] = 0;
            continue;
        }
        
        if(lost[i]< n&&reservePossible[lost[i]+1] == 1){
            //오른쪽 친구에게 빌릴 수 있는 경우 
            reservePossible[lost[i]+1] = 0;
            continue;
        }
        //양 옆 친구한테 못빌렸으면 체육복 없는 친구가 한명 생긴것
        answer++;
    }
    return n-answer;
}