[Programmers] 체육복(C++)

I 문제 소개

---

문제 설명

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다.

예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

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

제한사항

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

 

---

II 문제 풀이

---

최근 백준에서 풀었던 탐욕법(그리디 알고리즘)과 관련된 문제이다.

가장 많은 학생이 수업을 체육 수업에 참가하려면 어떻게 해야할까?

 

→ 여벌 체육복을 가진 학생들이 최대한 나눠주면 된다.

(최선의 선택)

 

0. 초기 환경 설정

---

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

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
	int answer = 0;
	vector<int> student;
	int i;
	
	student.push_back(0);

	for (i = 0;i < n;i++)
		student.push_back(1);
	for (i = 0;i < lost.size();i++)
		student[lost[i]]--;
	for (i = 0;i < reserve.size();i++)
		student[reserve[i]]++;

	return answer;
}

n의 크기의 벡터 student를 만들어 모든 학생들이 각자 지니고 있는 체육복의 수를 저장할 수 있게 했다.

처음에 모두 한개씩 갖고 있다가, 잃어버린 학생들은 1개를 빼주고 여벌이 있는 학생들은 1개를 더해줬다.

(문제의 조건 중, 여벌이 있는 학생도 잃어버릴 수 있다고 하였으므로 0개와 2개로 초기화하는 게 아니라 연산을 해주었다.)

 

처음에 0을 push_back해준 것의 의미

: 벡터는 0부터 시작인데, 문제에서는 1부터 시작하게 해서 아무 의미 없는 0을 넣어주었다. 왜냐하면 마지막에 answer를 계산할 때 체육복을 갖고 있는 개수가 0개가 아닌 학생의 수를 세면 되기 때문이다.

 

1. 체육복 나눠주기

---

for (i = 0;i < student.size();i++)
{
	if (student[i] == 2)
	{
		if (i > 1 && student[i - 1] == 0)
		{
			student[i]--;
			student[i - 1]++;
		}
		else if (i < student.size() - 1 && student[i + 1] == 0)
		{
			student[i]--;
			student[i + 1]++;
		}
	}
}

초기 환경 설정을 거치면 student 벡터에 저장되는 값들은 무조건 0, 1, 2중 하나일 것이다.

따라서 reserve벡터를 기반으로 접근을 할 게 아니라, student벡터를 전체적으로 탐색해보면서 값이 2인 부분을 찾아서 앞번호나 뒷번호 값이 0이면 하나씩 더하고 빼주면 된다.

 

이 때 주의할 점은, student 벡터의 0번째 원소는 처음에 우리가 임의로 넣어준 가짜값이라 건들면 안되는 것이고, i가 마지막인데 i+1을 접근하면 메모리 참조 오류이므로 조건문으로 잘 제어한다.

 

2. 계산

---

answer = 0;
for (i = 0;i < student.size();i++)
{
	if (student[i] != 0)
		answer++;
}

나눠주는 것은 끝났으므로 student를 탐색해 0이 아닌 원소의 개수만 세주면 끝난다.

0을 기준으로 삼은 이유는 앞에서 말했다시피 처음에 준 가짜값이 0인 것도 있어서 삼은 것이다.

 

3. 최종

---

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

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
	int answer = 0;
	vector<int> student;
	int i;
	
	student.push_back(0);

	for (i = 0;i < n;i++)
		student.push_back(1);
	for (i = 0;i < lost.size();i++)
		student[lost[i]]--;
	for (i = 0;i < reserve.size();i++)
		student[reserve[i]]++;

	for (i = 0;i < student.size();i++)
	{
		if (student[i] == 2)
		{
			if (i > 1 && student[i - 1] == 0)
			{
				student[i]--;
				student[i - 1]++;
			}
			else if (i < student.size() - 1 && student[i + 1] == 0)
			{
				student[i]--;
				student[i + 1]++;
			}
		}
	}
	answer = 0;
	for (i = 0;i < student.size();i++)
	{
		if (student[i] != 0)
			answer++;
	}
	return answer;
}

최종 코드다.

명료해서 따로 덧붙일 말이 없다.

 

III 느낀점

---

level 1 문제 답게 문제만 따라가도 풀 수 있었다.

백준까지 여러 개의 그리디 알고리즘문제를 풀어봤는데, 아직도 사실 감이 잘 오지 않는다.

알고리즘이 명확하지 않고 추상적이라 더 그런 것 같다. 공부가 더 필요할 듯..

 

 

 

 

 

 

 

 

 

Coding Space by MIR :

Programmers 체육복 C++

프로그래머스 체육복 C++