강의로 돌아가기
lamerGit

시간초과가 나오는데 어디가문제일까요?

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

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    int size=scoville.size();
    for(int i=0; i<size-1; i++)
    {
        sort(scoville.begin(),scoville.end());
        if(scoville[0]<K)
        {
            answer++;
            scoville[0]=scoville[0]+(scoville[1]*2);
            scoville.erase(scoville.begin()+1);
        }
    }
    if(scoville[0]<K)
    {
        return -1;
    }

    return answer;
}

효율성에서 시간초과로 실패하네요ㅠ

  • 심승현
    sort때문에 그럴거에요. C++는 어떤 sort방식을 채택하는지는 모르지만, 대개 NlongN속도로 정렬을 하게되는데 이것도 빠르다고 생각하지만, Heap (우선순위 큐)를 사용하면 logN의 시간복잡도로 삽입,삭제를 할 수 있다고 하네요. 이문제는 우선순위 큐를 써야 할 것 같네요. 심승현 2018.10.26 17:19
1 개의 답변
Demi

안녕하세요. 본 문제는 O(nlogn)으로 풀어야합니다.

작성하신 코드는 O( n2 logn) 이네요. :)
문제의 카테고리를 잘 보시고 다른 방법을 고안해보세요.

답변 쓰기
이 입력폼은 마크다운 문법을 지원합니다. 마크다운 가이드 를 참고하세요.