[프로그래머스] 디펜스 게임 c++

*O(nlogn)안에 풀어야 할 때 최소 힙 생각하기

풀이    <최소힙에 있는 값은 "무조건"을 사용한다.>

1.최소 힙을 통해서 enemy 벡터를 앞에서부터 정렬해준다.

2. 최소힙의 사이즈가 k개가 넘어가면 최소힙의 제일 작은 원소 즉 0번째 값을 삭제하고 sum에 더한다. (top(), pop() 사용)

3. sum이 n보다 커지면 for문을 탈출한다. 이때 i값이 답.

모든 라운드를 막을 수 있을때는  enemy의 size 반환.

 

**제일 큰 k개에 "무조건"을 써야되기 때문에 최대힙을 써야할줄 알았는데 최소힙을 써야했다.
왜냐하면 pop()을 할때 맨 앞에 있는 원소를 삭제하는데 제일 작은 원소를 삭제하기 위해서이다.

#include <string>
#include <vector>
#include<queue>
using namespace std;


int solution(int n, int k, vector<int> enemy) {
    int answer=0;
    priority_queue<int, vector<int>, greater<int>> num;
    
    int size=enemy.size();
    int sum=0;
    for(int i=0;i<size;i++)
    {
       
        num.push(enemy[i]);
        k--;
        if(k<0)
        {
            sum+=num.top();
            num.pop();
        }
         if(sum>n)
        {
            answer=i;
            break;
        }
      
    }
    if(answer==0)
        answer=size;
   return answer;
}

 

 

 

테스트 3,6 시간초과 코드

질문하기 봤는데 최소힙 문제 같아서 다시 짜야했다.

풀이

1.enemy의 값이 n보다 커지는 부분을 찾는다. (num에 저장)

2.  그 부분을 정렬한다. 

3. 그 부분 다음부터 하나씩 삽입하며 내림차순으로 정렬한다.

4.  num에서 k 개 만큼 deNum에 저장하고 temp-deNum>n보다 커지게 되면 break; (temp는 0부터 i까지 enemy의 값)

#include <string>
#include <vector>
#include<algorithm>

using namespace std;

vector<int>num;//적의 숫자를 오름차순으로 정렬
int kk;
void insert(int t)
{
    vector<int>::iterator it = num.begin();
    for(int i=0;i<kk+2&&i<num.size();i++)
    {
        if(t>num[i])
        {
            num.insert( it+i, t );
            return;
        }
    }
    num.push_back(t);   
}
int solution(int n, int k, vector<int> enemy) {
    kk=k;
    int answer = 0;
    int temp=0;
    int size=enemy.size();
    int i=0;
    
    for( i=0;i<size;i++){
        
        temp+=enemy[i];
        num.push_back(enemy[i]);
        if(temp>n)
            break;
      
            
    }
   
    sort(num.begin(),num.end(),greater<int>());
   
    
    int deNum=0;
 
    while(i<size)
    {
        
        
        deNum=0;
        for(int j=0;j<k&&j<num.size();j++)
        {
            deNum+=num[j];

         }
        
        
        if(temp-deNum>n)
        {
            answer=i;
            
            break;
        }
        insert(enemy[++i]);//새로운 수 넣어서 정렬
        temp+=enemy[i];
        
    }
   if(i==size)
       answer=size;
   return answer;
}