LV1.체육복

https://school.programmers.co.kr/learn/courses/30/lessons/42862

프로그래머스

---

문제 내용 :

1.체육복이 없는 학생에게 여벌의 체육복이 있는 학생들이 빌려줄 수 있음

1-1.하지만 빌려줄수 있는 경우는 자기 앞 또는 뒤 학생한테만 체육복을 빌려 줄 수 있음

2.체육복은 가지고 있지만 한벌만 가지고있으면 빌려 줄수 없음

3.체육복을 가지고 있어야만 수업을 들을 수 있음

4.여벌 체육복을 갖고있지만 체육복을 한벌 잃어버릴 수 있음

이때 수업을 들을 수 있는 학생의 최대값을 return

---

풀이 : map자료구조 

학생을 나타내는 key , 체육복의 갯수 value 데이터가 필요하기에 map 자료구조를 활용

1.체육복이 없는 학생들(lost)

2.여벌체육복이 있는 학생들(reserve)

이 두 무리를 하나의 map으로 정리한다.

이 map에 존재 하지 않는 학생은 수업을 들을 수 있는 학생이고

이 map에 있는 학생들에 대해서만 체크하면 된다.

 

그후 map을 학생수(n)만큼 순회하며 앞,뒤를 체크하며 체육복 수를 조정하면 된다.

 

코드 영역

#include <string>
#include <iostream>
#include <vector>
#include <map>

using namespace std;

//체육복 빌려주는 조건 : 자기 앞,뒷 1번호 만큼 가능
//체육수업을 들을수있는 학생의 최댓값 return 
//여벌 체육복을 가져온 학생도 도난 가능,체육복을 빌려줄수 없음 하지만 자기것는 있음

bool reserve_check(int index, map<int,int>& students)
{
    //iter = 자신의 앞 또는 뒤 학생의 iter
    map<int,int>::iterator iter_before = students.find(index);
    
    //해당 학생이 없을수도 있기에(제일 앞학생 또는 제일 뒷학생 고려)
    //여벌 체육복이 있으면 해당 학생의 체육복을 -1 시킴
    if(iter_before  != students.end() && iter_before->second == 2)
    {
        iter_before->second--;
        return true;
    }  
    
    return false;
}


int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    
    map<int,int> students; //학생번호,체육복 수
    
    //여벌 체육복이 있는 학생을 맵에 추가
    for(int num : reserve) {  students.insert({num,2}); }
    
    //체육복을 잃어버린 학생을 맵에 추가
    for(int num : lost)
    {
        //해당 맵에 여벌 체육복을 갖고 있지만 잃어버린 학생이 있을수 있기에 find 실행
         map<int,int>::iterator iter = students.find(num);
        //find결과가 없으면 해당 체육복이 없는 학생으로 추가
        if(iter  == students.end()) {  students.insert({num,0}); }
        //find 결과가 있으면 해당 학생의 체육복 수를 1감소
        else {  iter->second--;}
    }
    
    for(int i=1; i <= n ; i++)
    {
        map<int,int>::iterator iter = students.find(i);
        
        //해당 학생이 map에 없으면 수업을 들을 수 있기에 answer후 순회
        if(iter == students.end()) {  answer++;  continue;}
        
        //해당 학생이 체육복이 없는경우
        if(iter->second == 0)
        {
            //자기 앞,뒷 번호의 여벌 체육복을 체크후 true인경우 해당 학생의 체육복을 1증가
           if(reserve_check(i-1,students) || reserve_check(i+1,students))  iter->second++; 
        }
        
        //해당 학생이 체육복이 1개 이상인경우 answer증가 
        if(iter->second >=1) {  answer++; } 
        
    }

    
    
    return answer;
}