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

https://programmers.co.kr/learn/courses/30/lessons/42862?language=cpp 

코딩테스트 연습 - 체육복

 

전체 코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    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])
            {
                lost.erase(lost.begin()+i);
                reserve.erase(reserve.begin()+j);
                i--; j--;
            }
        }
    }
    
    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])
            {
                lost.erase(lost.begin()+i);
                reserve.erase(reserve.begin()+j);
                i--; j--;
                break;
            }
        }

    }
    
    answer = n-lost.size();
    return answer;
}

 

정렬을 왜 해주는가?

최대한 많은 학생이 체육복을 입기 위해 먼저 왼쪽의 친구에게 빌려보고 없다면 오른쪽 친구에게 빌려서

규칙적으로 빌림으로써 최대한 많은 학생들이 체육복을 빌려 입을 수 있는 것이다.

불규칙적으로 빌린다면 아래와 같은 상황에서 모두 체육복을 입을 수 있지만, 그렇지 못한 상황이 만들어질 것이다.

 

( 여분이 있는 학생은 동그라미로, 체육복을 빌려야 하는 학생은 밑줄, 자기 것만 있는 학생은 아무 표시도 하지 않음 )

-> 여기서 2의 학생이 1의 학생에게 빌리고 4의 학생은 3의 학생에게 빌린다면 모두 체육복을 입을 수 있지만,

2의 학생이 3의 학생에게 빌려버리면 4의 학생은 빌리지 못하는 상황이 발생한다.

그래서 왼쪽의 학생에게 먼저 빌리고 오른쪽의 학생에게 빌려보는 상황을 만들기 위해 정렬하여

차례대로 탐색하는 것이다.

 

아래의 부분은 왜 필요한가?

    for(int i=0;i<lost.size();i++)
    {
        for(int j=0;j<reserve.size();j++)
        {
            if(lost[i]==reserve[j])
            {
                lost.erase(lost.begin()+i);
                reserve.erase(reserve.begin()+j);
                i--; j--;
            }
        }
    }

위 코드가 없이

이 부분을 추가하여

같은 번호라면 지우는 상황을 추가해주어

아래의 코드를 실행을 한다면 될 것 같지만 한 가지 문제가 생긴다.

    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]||lost[i]==reserve[j])
            {
                lost.erase(lost.begin()+i);
                reserve.erase(reserve.begin()+j);
                i--; j--;
                break;
            }
        }

    }

 

 

아래의 그림에서 순차적으로 ( L : lost, R : reserve )

코드를 실행한다면, 4의 학생의 경우 누구에게도 빌려주지 못하는 학생이지만

3의 학생에게 빌려주는 상황이 카운트된다.

 

최종적으로 lost 학생이 reserve 학생에게 빌려 lost 벡터와 reserve 벡터를 하나씩 지워질 것이다.

그러면 lost 벡터에 남아 있는 학생들은 체육복을 빌릴 수 없는 학생들이 되므로

정답은 N명의 학생에서 lost 벡터에 남아 있는 학생들의 수가 된다.