프로그래머스 디펜스 게임 C++

 

처음엔 시간초과가 떴었다.

왜 그런가 하니, 내가 처음에 구성했던 코드는

 

n 최대 = 1,000,000,000

enemy 최대 = 1,000,000

 

둘을 이중포문으로 구성한 코드였다.

 

 

넣고, 첨부터 검사하고

넣고, 첨부터 검사하고

 

이런식이었으니 문제가 되었다.

따라서 최소한으로 검사하는 방법을 사용하고자 최솟값을 이용했다.

 

#include <string>
#include <vector>
#include <set>

using namespace std;

int solution(int n, int k, vector<int> enemy) {
    
    multiset<int> im; // 가장 큰 정수 k개를 담고 있을 set. 무적권을 사용할 것들.
    int imSize = 0;
    
    long long totalEnemy = 0;
    
    // 잘 구성하지 않으면 1,000,000 x 500,000 = 시간초과
    
    int round; // round
    
    for(round = 0; round < enemy.size(); round++) {
        
        
        if(imSize < k) {
            im.insert(enemy[round]);
            imSize++;
        } else if( (*im.begin()) < enemy[round] ) {
            totalEnemy += (*im.begin());
            im.erase(im.begin());
            im.insert(enemy[round]);
        } else {
            totalEnemy += enemy[round];
        }
        
        if(totalEnemy > n)
            break;
    }

    return round;
}