[2025.02.03] 체육복

문제 설명

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

 

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최대값을 return 하도록 solution 함수를 작성해주세요.

 

 

제한사항

• 전체 학생의 수는 2명 이상 30명 이하입니다.
• 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
• 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

 

 

입출력 예

n			lost	reserve	return	설명
5			[2, 4]	[1, 3, 5]	5	1번 학생이 2번 학생에게 체육복을 빌려주고, 3번 학생이나 5번 학생이 4번 학생에게 체육복을 빌려주면 학생 5명이 체육수업을 들을 수 있습니다.
5			[2, 4]	[3]	4	3번 학생이 2번 학생이나 4번 학생에게 체육복을 빌려주면 학생 4명이 체육수업을 들을 수 있습니다.
3			[3]	[1]	2	-

 

 

문제 풀이

풀이 언어 : C++

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

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    vector<int> students(n, 1); // 학생별 가진 체육복의 수
    
    // lost, reserve 정렬
    sort(lost.begin(), lost.end());
    sort(reserve.begin(), reserve.end());
    
    // 체육복 보유수 업데이트
    // 여벌 적용
    for(int student_num : reserve)
    {
        students[student_num-1]++;
    }
    // 도난 적용
    for(int student_num : lost)
    {
        students[student_num-1]--;
    }
    
    // 체육복 빌리기
    for(int student_num : lost) // 도난 당한 사람들 중
    {
        // 체육복이 없는 사람들
        if(students[student_num-1]==0)
        {
            if(students[student_num-2]==2) // 앞에 사람이 여벌이 있는 경우
            {
                students[student_num-1]=1;
                students[student_num-2]=1;
            }
            else if(students[student_num]==2) // 뒤에 사람이 여벌이 있는 경우
            {
                students[student_num-1]=1;
                students[student_num]=1;
            }
            else // 여벌이 앞뒤 사람 모두 없는 경우
            {
                students[student_num-1]=0;
            }
        }
        
    }
    
    // 체육 수업을 들을 수 있는 학생수 계산
    int not_have_uniform_count=count(students.begin(), students.end(), 0); // 체육복이 없는 학생수
    answer=n-not_have_uniform_count; // 체육복이 있는 학생수
    return answer;
}

 

 

일단 각 학생들이 몇 벌의 체육복을 가지고 있는지 적어놓을 공간이 필요하다. students int형 벡터를 선언해주고 모두 체육복을 한 벌씩 가지고 있는 것으로 초기화해준다. 그리고 매개변수로 주어진 데이터 reserve와 lost는 사용하기 전 각각 오름차순으로 정렬해준다. 이제 여벌을 가지고 있는 학생들과 도난 당한 학생들의 체육복 수를 업데이트해준다. 여벌이 있는 학생은 체육복 수를 하나 늘려주고 도난 당한 학생은 체육복 수를 하나 줄여준다. 이렇게 하면 서로 빌리고 빌려주기 전 학생들이 체육복을 어떻게 가지고 있는지 알 수 있다.

 

그 다음 이제 체육복을 빌려주면 된다. lost에 들어있는 학생들 중에만 체육복의 수가 0인 학생들이 있을 것이기 때문에 lost에 있는 학생들만 for문을 돌려준다. 체육복이 없는 사람 즉 students[student_num-1]이 0인 사람에 한에서만 체육복 빌리기를 진행한다. 여벌이 있는데 체육복 한 벌을 도난당한 사람을 제외하기 위한 조건문이다. 이제 앞에 있는 사람에게 먼저 빌릴 수 있는지 확인하고 없다면 뒤에 사람을 확인한다. 둘다 없다면 체육복이 없는 것으로 0으로 표시한다. 반드시 앞에서부터 확인해야 한다. lost를 모두 오름차순으로 정렬했기 때문에 앞에서부터 뒤로 넘어오면서 체육복의 유무를 확인할 것인데 이 때 뒤에서 체육복을 빌려버리면 최대값이 나오지 않을 수 있다.

 

마지막으로 체육복이 한 벌이라도 있으면 수업에 참여할 수 있기 때문에 체육복이 0인 사람들을 count() 함수를 이용해 구해준다. 그리고 전체 학생수 n에서 체육복이 없는 사람들을 빼면 체육수업에 참여할 수 있는 사람들을 구할 수 있다.

 

 

오답 노트

여벌을 가진 학생도 도난당할 수 있는다는 경우를 생각하지 못하고 여벌이 있다면 체육복 벌수를 2로 고정, 없다면 0으로 고정해서 문제가 발생하였다. 이후 증감연산자로 교체하여 문제를 해결하였다.

vector<int> students(n, 1);
    
for(int student_num : reserve)
{
    students[student_num-1]=2;
}

 

최대값을 구하기 위해서는 정렬이 중요한 것을 알고 있었지만 매개변수가 정렬되지 않고 주어질 수 있는 경우는 생각하지 못했다. 그런 경우 테스트 케이스 실패가 발생하여 reserve와 lost 모두 사용 전 정렬을 진행하였다.

// lost, reserve 정렬
sort(lost.begin(), lost.end());
sort(reserve.begin(), reserve.end());

 

 

문제 링크

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

프로그래머스