Level 1 체육복

시간 복잡도: O(N)

1#include <string>
2#include <vector>
3
4using namespace std;
5
6int solution(int n, vector<int> lost, vector<int> reserve) {
7  int answer = 0;
8
9  vector<int> roster(n, 1);
10  for(int a : reserve) ++roster[a-1];
11  for(int a : lost) --roster[a-1];
12  for(int i=0; i<n; ++i) {
13    if(roster[i]) ++ answer;
14    else {
15      if(i-1 >= 0 && roster[i-1] > 1) {
16        ++answer;
17        roster[i]++;
18      }
19      else if(i+1 < n && roster[i+1] > 1) {
20        ++answer;
21        roster[i]++;
22        roster[i+1]--;
23      }
24    }
25  }
26  return answer;
27}

체육복을 가지고 있는 경우 바로 +1을 한다. 체육복이 없는 경우 이전과 다음 학생을 확인, 여유분이 있으면 +1 해준다.