[프로그래머스] 체육복

코딩테스트 연습 - 체육복

풀이

학생수가 최대 30명 이하이므로 그리디(탐욕법) 알고리즘을 활용했다.
1번 학생부터 n번 학생까지 체육복을 빌려줄 때, 앞번호->뒷번호 순서대로 체육복 개수를 확인하고 빌려줘야 최대한 많은 학생들이 체육복을 입을 수 있다.

시간 복잡도

• 그리디 알고리즘 : O(n)
  -> 학생 수 n명에 비례한다.
• reserve 벡터 정렬을 활요한 풀이 : O(nlogn)
  -> 정렬할 때 nlogn이 된다( r.insert(x)부분 )

코드

그리디 알고리즘을 활용한 풀이

#include <vector>

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    vector<int> check(n+2,1);
    for(auto& i : reserve) check[i]++;
    for(auto& i : lost) check[i]--;
    for(int i = 1 ; i <= n ; i++){
        if(check[i] == 2){
            if(check[i-1] == 0) check[i-1] = check[i] = 1;
            else if(check[i+1] == 0) check[i+1] = check[i] = 1;
        }
    }
    for(int i = 1 ; i <= n ; i++) if(check[i] > 0) answer++;
    return answer;
}

reserve 벡터의 정렬을 활용한 풀이

 #include <vector>
 #include <unordered_set>
 #include <set>
 
 using namespace std;
 
 int solution(int n, vector<int> lost, vector<int> reserve) {
     unordered_set<int> l(lost.begin(), lost.end());
     set<int> r;
     unordered_set<int> inter;
     
     for(auto& x : reserve){
         if(l.find(x) != l.end()) inter.insert(x);
         else r.insert(x); // klogk 정렬을 해야 하므로
     }
     for(auto& x : inter) l.erase(x);
     
     for(auto& x : r){
         if(l.find(x-1) != l.end()) l.erase(x-1);
         else if(l.find(x+1) != l.end()) l.erase(x+1);
     }
     
     return n - l.size();
 }