[알고리즘문제] 프로그래머스 더 맵게

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

코딩테스트 연습 - 더 맵게

 

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

using namespace std;

bool check(vector<int> scoville, int K) {
    for (int i = 0; i < scoville.size(); i++) {
        if (scoville[i] < K) {
            return false;
        }
    }
    return true;
}

int solution(vector<int> scoville, int K) {
    int count = 0;
    if (scoville.size() <= 1) {
        count = -1;
        return count;
    }

    sort(scoville.begin(), scoville.end());
    while (1) {
        if (count != 0) {
            sort(scoville.begin(), scoville.end());
        }
        if (check(scoville, K) == true) {
            break;
        }
        else {
            if (scoville.size() <= 1) {
                count = -1;
                break;
            }
        }
        
        count++;
        int result = 0;
        result = scoville[0] + (scoville[1] * 2);
        scoville.erase(scoville.begin(), scoville.begin()+2);
        scoville.insert(scoville.begin(), result);
    }
    return count;
}

프로그래머스 heap 카테코리의 문제 더 맵게를 풀어보았다.

scoville 배열을 sorting한 후  K보다 작은 수가 존재하지 않을때 까지 연산을 반복하며(단, K보다 작은수가 존재하지만 더이상 연산할 수 없을 경우 -1을 return),  연산 횟수를 return한다.

하지만 현재 code로는 효율성에서 실패하였다. vector 배열이 길어지면 sort의 효율성이 떨어지는 듯 하다.

vector를 sort하는 방법이아닌 우선순위 큐를 이용하기로 했다.

 

#include <vector>
#include<queue>

using namespace std;

int solution(vector<int> scoville, int K) {
    if (scoville.size() <= 1) {
        return -1;
    }
    int answer = 0;
    int first, second;

    priority_queue<int, vector<int>, greater<int>> sort(scoville.begin(), scoville.end());
    while (sort.top() < K && sort.size() > 1) {
        first = sort.top();
        sort.pop();
        second = sort.top();
        sort.pop();
        sort.push(first + (second * 2));

        answer++;
    }
    if (sort.top() < K) {
        return -1;
    }
    return answer;
}

 

 

우선순위 큐를 오름차순으로 선언하면 큐의 가장 첫번째, 두번째에 숫자가 낮은 순서대로 정렬이 된다.

그런다음 첫번째, 두번째 값을 추출하여 연산 한 후 반복문 내에서 비교하여 연산 횟수를 return한다.

첫번째 코드는 배열을 sort하며 배열 내에서 시프트 연산이 일어나고 또한 2중 반복문을 사용하게 되므로 시간 효율성이 상당히 떨어진다. 

두번째 코드는 우선순위 큐를 이용하여 단 한번 정렬이 되고 데이터의 push, pop에 드는 비용또한 적게 드므로 효율성이 높다고 볼 수 있다.