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

programmers.co.kr/learn/courses/30/lessons/42626

코딩테스트 연습 - 더 맵게

loop마다 매번 정렬을 하면 nlogn시간을 소모한다. 효율성 시험을 통과하기 위하여 priority_queue나 heap을 사용해주면 된다.

heap을 사용하면 매번 begin~end까지 모든 요소를 입력하기 떄문에 귀찮다. priority_queue를 훨씬 간단하게 쓸 수 있다.

bool compare(int a, int b){
    return a>b;
}

int solution(vector<int> scoville, int K) {
    int count = 0;
    make_heap(scoville.begin(),scoville.end(),compare);

    int temp;
    while(scoville.size()>1){
        pop_heap(scoville.begin(),scoville.end(),compare);
        int s1 = scoville.back();  scoville.pop_back();
        pop_heap(scoville.begin(),scoville.end(),compare);
        int s2 = scoville.back();  scoville.pop_back();

        if(s1>=K && s2>=K) break;
        count++;
        temp = s1+s2*2;

        scoville.push_back(temp);
    }
    return temp>=K? count:-1;
}

priority_queue를 쓰면 make_heap를 훨씬 쓰기 쉽다. priority_queue는 내부적으로 make_heap을 사용한다.

    int solution(vector<int> scoville, int K) {
        priority_queue<int,vector<int>,greater<int>> pq(scoville.begin(),scoville.end());

        int temp,count=0;
        while(pq.size()>1){
            int s1 = pq.top(); pq.pop();
            int s2 = pq.top(); pq.pop();
            if(s1>=K && s2>=K) return count;
            count++;
            temp = s1+s2*2;
            pq.push(temp);
        }
        return temp>=K? count:-1;
    }

 

 처음 떠올린 풀이는 vector를 작은 순서로 정렬한 후 제일 작은 값 2개를 문제의 조건에 따라 변환시키는 방법이었다. 이 경우에 문제의 조건을 만족시키지 못하는 경우가 생겼다. { 1, 1, 2 }, K=3 일때

첫 번째 for loop에서 { 3,2}가 된다. 여기서 한 번 더 정렬을 해주지 않으면

틀린 정렬이 나온다. 제일 작은 값이 3이 되어 3+2*2가 다음 값이 된다.

옳은 정렬은 제일 작은 값이 2가 되어 2+3*2가 다음 값이 되어야 한다.

다음은 효율성 테스트를 통과하지 못한 코드이다

    bool compare(int a, int b){
        return a>b;
    }

    int solution(vector<int> scoville, int K) {
        int count = 0;
        int temp;
        
        while(scoville.size()>1){
            sort(scoville.begin(), scoville.end(), compare);

            int smallest = scoville.back(); scoville.pop_back();
            int small = scoville.back();    scoville.pop_back();
            if(smallest>=K && small>=K) break;

            temp = smallest + small*2;
            scoville.push_back(temp);
            count++;

        }
        return temp>=K? count : -1;
    }