프로그래머스 귤고르기 c++ // 공간복잡도 공식, 구현

https://school.programmers.co.kr/learn/courses/30/lessons/138476

프로그래머스

1. 공간복잡도 공식

512MB == int배열[1억] 임을 기억하자.

 

2. 의사코드

1. arr을 정렬함 //a[i] : i의 등장횟수

ex) arr : 2 2 2 1 1

   k=6,  O  O  O

2. k와 arr[i]를 -하면서 k가 0이될때까지 뺴면됨.

3. arr[i]가 0이될때마다 ret++

4. k가 0이되면 종료 and 마지막 0이된숫자를 세주기위해 ret+1

 

3. 전체코드

#include <bits/stdc++.h>

using namespace std;

int a[10000000+1]; //a[1] : 1의 등장횟수
int ret;

int solution(int k, vector<int> tangerine) {
    int answer = 0;
    for(auto i : tangerine){
        a[i]++;
    }
    
    sort(a,a+10000000+1,greater<int>());
    
    int i=0;
    while(true){
        if(k==0) break;
        if(a[i]==0) {
            i++;
            ret++;
            continue;
        }
        a[i]--;
        k--;
        
    }
    
    return ret+1; //마지막 0반영
}