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

문제 설명

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 solution함수의 매개변수로 주어질 때, 체육복을 입은 채로 체육 수업을 들을 수 있는 최대 학생 수를 return하시오. (단, 여벌의 체육복은 항상 한 벌만 가져오며, 이웃하는 번호를 지닌 학생들끼리만 여벌의 체육복을 빌려줄 수 있다.)

 

입출력 예

lost = { 2, 3 }, reserve = { 1, 2 }일 때, 

1번 학생은 체육복을 "기본 1벌" + "reserve 1벌" = 2벌 갖고 있고,

2번 학생은 "기본 1벌" + "reserve 1벌" - "잃어버림 1벌" = 1벌 갖고 있고,

3번 학생은 "기본 1벌" - "잃어버림 1벌" = 0벌 갖고 있다.

 

이때, 이웃하는 번호를 지닌 학생들끼리만 체육복을 빌려줄 수 있으므로,

체육복을 2벌 갖고 있는 1번 학생이라 할지라도 3번 학생에게 체육복을 빌려줄 수 없다.

따라서 체육복을 입은 채로 체육 수업을 들을 수 있는 최대 학생 수는 1번, 2번 학생으로 2이다. 

 

 

풀이

1. 일단 모든 학생들이 1벌이 체육복을 가져왔다고 가정하고, cloth_count의 모든 원소(=학생 번호)에 1을 넣어준다.

 

2. 이러한 cloth_count 배열에서, 체육복을 잃어버린 학생들은 cloth_count를 -1씩 해준다.

 

3. 여벌의 체육복을 가져온 학생들에 대해선 cloth_count를 +1씩 해준다.

 

4. 이후 cloth_count가 0인 학생들이 다른 학생들로부터 체육복을 빌릴 수 있는지 확인한다. 

 

코드

#include <string>
#include <vector>

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve)
{
    vector<int> cloth_count;
    for (int i = 0; i < n; i++)
        cloth_count.push_back(1);
    for (int i = 0; i < lost.size(); i++)
        cloth_count[lost[i] - 1]--;
    for (int i = 0; i < reserve.size(); i++)
        cloth_count[reserve[i] - 1]++;

    for (int i = 0; i < n; i++)
    {
        if (cloth_count[i] == 0)
        {
            if (i - 1 >= 0 && cloth_count[i - 1] >= 2)
            {
                cloth_count[i - 1]--;
                cloth_count[i]++;
            }
            else if (i + 1 < n && cloth_count[i + 1] >= 2)
            {
                cloth_count[i + 1]--;
                cloth_count[i]++;
            }
        }
    }

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