[Programmers/C++] 체육복

시간 복잡도

• 모든 학생을 탐색하는 방법으로 $O(n)$ 의 시간 복잡도가 발생합니다.

문제 접근법

• 학생들의 체육복 개수를 0(체육복 있음)으로 초기화 합니다.
• 체육복을 도난당한 학생은 -1, 여분의 체육복을 가져온 학생은 +1 합니다.
• 이후 학생들의 체육복 개수는 -1(체육복 없음), 0(체육복 있음), 1(체육복, 여벌복 있음) 으로 나뉘게 됩니다.
• 이후 모든 학생들을 탐색하며 체육복이 없다면 앞, 뒤 학생에게 체육복을 빌리면 됩니다.
• 학생의 체육복 개수가 0개 이상이라면 정답을 하나 증가시킵니다.

코드

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

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    
    int count[31]={};

    for(int i=0; i<lost.size(); i++)
        count[lost[i]]--;
        
    for(int i=0; i<reserve.size(); i++)
        count[reserve[i]]++;
    
    for(int i=1; i<=n; i++)
    {   
        if(count[i]==-1)
        {
            if(count[i-1]==1)
            {
                count[i]=0;
                count[i-1]=0;
            }
            else if(count[i+1]==1)
            {
                count[i]=0;
                count[i+1]=0;
            }
        }
        if(count[i]>=0)
            answer++;
        
    }
    
    return answer;
}