더 맵게

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

프로그래머스

 

풀이 :

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

using namespace std;


int solution(vector<int> scoville, int K) 
{
    int answer = 0;

    sort(scoville.begin(), scoville.end(), greater<int>());

    while (false == (scoville.back() >= K) || false == (scoville[scoville.size()-2] >= K))
    {
        if (scoville.size() <= 2)
        {
            return -1;
        }
        // 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수(a) + (두 번째로 맵지 않은 음식의 스코빌 지수(b) * 2)
        int a = scoville.back();
        int b = scoville[scoville.size() - 2];
        int newscoville = a + b * 2;

        scoville.erase(scoville.end() - 2, scoville.end());
        scoville.push_back(newscoville);
        answer++;
        sort(scoville.begin(), scoville.end(), greater<int>());
    }

    return answer;
}

효율성테스트 전부실패, 26개 케이스중 3개 실패.

 

개선점 :

1. 정렬 방법:
   • 나 : 각 반복문 내에서 벡터를 sort 하여 정렬합니다. 이는 매번 벡터 전체를 정렬하기 때문에 비효율 적입니다.
   • 개선 : 최소 힙을 사용하여 항상 가장 작은 두 개의 요소를 O(log n)시간 복잡도로 효율적으로 정렬합니다.
2. 효율성:
   • 나 : sort 함수의 시간복잡도는 O(n log n)입니다 따라서, 벡터의 크기가 클수록 성능이 떨어질 수 있습니다. 특히 반복문 내에서 sort를 반복 호출하기 때문에 성능에 큰 영향을 미칩니다.
   • 개선 : 최소 힙을 사용하여 삽입과 삭제 연산이 O(log n)에 이루어집니다. 따라서 전체적으로 훨신 더 효율 적인 성능을 발휘합니다.
3. 종료조건:
   • 나 : scoville.back() >= K와 scoville[scoville.size()-2] >= K 를 통해 종료조건을 확인합니다. 이로 인해 두 번째로 맵지 않은 음식의 스코빌 지수가 충분히 높더라도 반복문이 종료되지 않을 수 있습니다.
   • 개선 : 최솟값을 중심으로 반복문을 돌기 때문에, 반복문을 탈출할 조건이 명확하고 최적화된 방식으로 처리.

 

 

개선된 코드 :

int solution(vector<int> scoville, int K) {
    priority_queue<int, vector<int>, greater<int>> minHeap(scoville.begin(), scoville.end());
    int mixCount = 0;

    while (minHeap.size() > 1) {
        int first = minHeap.top(); minHeap.pop();
        
        if (first >= K) {
            return mixCount;
        }
        
        int second = minHeap.top(); minHeap.pop();
        int newScoville = first + (second * 2);
        
        minHeap.push(newScoville);
        mixCount++;
    }

    if (minHeap.top() >= K) {
        return mixCount;
    } else {
        return -1;
    }
}

 

 

우선순위 큐를 사용하여 문제를 풀 수 있다.