[프로그래머스 C++] 더 맵게

안녕하십니까. Eun🦆입니다.

효율성 시간초과

 

[C++/문제풀이] C++을 무기로, 코딩테스트 광탈을 면하자! - Step3: 풀어서 내걸로 만들자! "더 맵게"

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<int> scoville, int K) {
    int answer = 0;
    sort(scoville.begin(),scoville.end());
    while(scoville[0]<K & scoville.size() > 1)
    {
        answer++;
        sort(scoville.begin(),scoville.end());
        //printf("scoville[0]=%d, scoville[1]=%d\n",scoville[0], scoville[1]);
        scoville.push_back(scoville[0]+scoville[1]*2);
        //printf("->scoville[0]=%d, size=%d\n",scoville[0],scoville.size());
        //printf("->scoville[%d]=%d\n",scoville.size()-1,scoville[scoville.size()-1]);
        scoville.erase(scoville.begin());
        scoville.erase(scoville.begin());
        //printf("->scoville[0]=%d, size=%d\n",scoville[0],scoville.size());
    }
    if(scoville[0]<K)
        return -1;
    return answer;
}
​
우선순위 queue를 사용해야 효율성을 통과한다.
차이는 정렬을 매번 하냐 안하냐의 차이! 
​
단지, 이 S/W에서 남는 것은 값을 변경할 때 index의 값을 직접 건드리면 안된다는 것!
​
통과 코드 : 
#include <string>
#include <vector>
#include <queue>
using namespace std;
int solution(vector<int> scoville, int K) {
    int answer = 0;
    // priority_queue<T, Container, Compare> : 원하는 자료형 T, vector 등 컨테이너, Compare 비교
    priority_queue<int, vector<int>, greater<int>> scov; ​// queue의 top로 계산하기 위해 역순으로
    for(int i=0;i<scoville.size();i++)
        scov.push(scoville[i]);
    while(scov.top()<K & scov.size()>1)
    {
        answer++;
        int a, b;
        a = scov.top();
        scov.pop();
        b = scov.top();
        scov.pop();
        scov.push(a+2*b);
    }
    if(scov.top()<K)
        return -1;
    return answer;
}

 

네이버 블로그 리뉴얼입니다.

(https://blog.naver.com/unsuk1/221980133230)