[프로그래머스 더맵게] c++ (풀이,코드, 효율성 해결 과정)

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/42626

프로그래머스

 

문제

풀이 및 코드

오류 코드 및 수정 내용

/*

스코빌 지수를 k이상 만듬

가장 맵지 x + (두번째 맵지x *2) -> k이상까지

k는 10억 이하 -> int가능

k이상 만들수 없을때 -1리턴

*/

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

int solution(vector<int> scoville, int K) {

    int answer = 0;

    int sum = 0;

       

    sort(scoville.begin(),scoville.end());

    if(scoville[0] >= K)

        return 0;

   

    while(1){

        //size가 1이라는 것은 이제 마지막이라는 것이고 &&이므로 첫번째이자 마지막 원소가 k보다 작으면 생성 불가

        if(scoville.size() <= 1 && scoville[0] < K)

            return -1;

        sum = scoville[0] + 2 * scoville[1];

        scoville.erase(scoville.begin(), scoville.begin() + 2);

        //삽입할 위치를 찾아서 넣기 위해 lower_bound사용 -> 벡터는 정렬되어있음

        auto it = lower_bound(scoville.begin(),scoville.end(),sum);

        scoville.insert(it,sum);

        answer++;

        if(scoville[0] >= K)

            break;

    }

    return answer;

}

결과는?

역시나 효율성에서 부서졌습니다.. ㅎㅎ
 
간단하게 처음에 sort를 진행하고 앞에 두개를 지우면서 계속 새로 갱신된 sum에 대해서 추가를 진행하였습니다.
 
굳이 따로 찾지 않고 lower_bound를 찾아 집어 넣는 방식을 했는데 생각을 해보니 역시 이렇게해서 바로 풀리면 알고리즘이 아니라는 것을 다시 깨달았습니다. (레벨2는 예상을 못하겠네..)
 

수정 코드 (우선순위 큐)

보통 이렇게 정렬이 되어있을때 우선순위 큐를 많이 쓰던것이 기억나 우선순위 큐를 진행하였습니다.
 
또한 우리는 높은것이 앞에가 아닌 낮은것이 우선순위큐의 top이 되어야 하니 역순으로 진행하였습니다.
 

#include <string>

#include <vector>

#include <algorithm>

#include <queue>

using namespace std;

int solution(vector<int> scoville, int K) {

    int answer = 0;

    int sum = 0;

    priority_queue<int,vector<int>, greater<int>> pq;

   

    for(int i = 0; i < scoville.size();i++){

        pq.push(scoville[i]);

    }

   

    while(1){

        if(pq.top() >= K)

            break;

        if(pq.size() <= 1 && pq.top() < K)

            return -1;

        sum = pq.top();

        pq.pop();

        sum += 2 * pq.top();

        pq.pop();

        pq.push(sum);

        answer++;

    }

   

    return answer;

}

우선순위 큐에 집어넣고 pq.top >=k라면 모든것이 k이상이니 충족 -> break
만약 마지막까지 k이상이 되지 않는다면 -> pq의 사이즈는 1이고 top이 <k일때 return -1을 기점으로 반복문을 돌렸습니다.