Contents
문제
문제를 보시려면 링크를 클릭해주세요.
풀이
탐욕법(그리디 알고리즘)을 이용하여 풀 수 있습니다.
체육복을 도난당한 학생은 -1, 여벌을 가지고 있는 학생은 +1을 해서 student 배열을 만들어줍니다.
- 도난당한 학생의 앞, 뒤 학생에게 여벌 체육복이 있는지 확인하는데, 이 때 앞 번호 학생이 우선적으로 빌려주게됩니다.
- 체육복을 빌려줬다면 그 학생도 -1 해줍니다.
- 결론적으로 도난당했으면 -1, 자신의 체육복이 있으면 0, 여벌까지 있으면 1값을 가지고 있습니다.
- 0이상의 값을 가진 학생이 체육수업을 들을 수 있는 학생입니다.
1번 학생의 앞 번호, n번 학생의 뒷 번호는 없지만 편의상 0으로 채워줌
student 배열 크기: n+2
소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <vector>
using namespace std;
int solution(int n, vector<int> lost, vector<int> reserve) {
int answer = 0;
vector<int> stu(n+2,0);
for(int i:lost){
stu[i]--;
}
for(int i:reserve){
stu[i]++;
}
for(int i=1; i<=n; i++){
if(stu[i]<0){
if(stu[i-1]==1){
stu[i]++;
stu[i-1]--;
}
else if(stu[i+1]==1){
stu[i]++;
stu[i+1]--;
}
}
}
for(int i=1; i<=n; i++){
if(stu[i]>=0)
answer++;
}
return answer;
}