99클럽 코테 스터디 7일차 TIL : 더 맵게

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

프로그래머스

참고로 저번기수때 풀었던 문제였다!

https://usowelcome.tistory.com/5

99클럽 코테 스터디 2일차 TIL : heap - 더 맵게 (미들러)

 

근데.... 효율성문제때문에 또 문제가 많았다!ㅎㅎ...

이전코드와 지금코드를 비교해봐야겠다ㅎㅎ

 

바로 푼것 -> 효율성에서 막힘

검색을 통해 다른방법을 생각 -> 통과!

이전에 만들었던 코드 -> 왜인지 모르지만 통과

이런 흐름이었다ㅎㅎ

---

[첫번째 시도] : 효율성에서 망함

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

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    
    make_heap(scoville.begin(), scoville.end(), greater<>());
    
    while(true){
        if(scoville[0] >= K){
            break;
        }
        if(scoville.size() < 2){
            return -1;
        }
        int a1 = scoville[0];
        pop_heap(scoville.begin(), scoville.end(), greater<>());
        scoville.pop_back();
        int a2 = scoville[0];
        pop_heap(scoville.begin(), scoville.end(), greater<>());
        scoville.pop_back();
        
        int newsco = a1 + (a2 * 2);
        scoville.push_back(newsco);
        make_heap(scoville.begin(), scoville.end(), greater<>());
        answer++;
        
    }
    
    return answer;
}

테스트케이스는 전부 통과하는데 효율성에서 막힌 코드이다.

사실 왜 문제인지 모르겠다...

heap도 잘 썼는데...... 매번 정렬해서? 근데 min heap을 유지하려면 저렇게 해야한다.,,

 

---

[두번째 시도] priority_que를 도입하자!

우선순위큐를 사용하면 효율성테스트를 통과한다는 글을 보았다.

근데,,, c++에서 우선순위큐는 힙으로 구현되어있는걸로 알고있는데?? 

그래도 일단 시도해봤다

근데...

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

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    
    priority_queue<int, vector<int>, greater<int>> myque(scoville.begin(), scoville.end());
    
    while(true){
        int a1 = myque.top();
        if(a1 >= K){
            break;
        }
        if(myque.size() < 2){
            return -1;
        }
        myque.pop();
        int a2 = myque.top();
        myque.pop();
        
        int newsco = a1 + (a2 * 2);
        myque.push(newsco);
        answer++;
        
    }
    
    return answer;
}

엥 통과했디;;;;;;;;;;;

왜???????

https://usowelcome.tistory.com/61

c++ priority_queue vs heap

바로바로 c++에서 우선순위큐와 힙의 시간복잡도에서 차이가 나기 때문이었다!

---

[세번째 시도] 근데 heap으로도 통과 되는데...

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

using namespace std;


int solution(vector<int> scoville, int K) {
    int answer = 0;
    make_heap(scoville.begin(), scoville.end(),greater<>{});

    while(true){
        if(scoville[0] >= K){
            break;
        }
        if(scoville.size() < 2){
            answer = -1;
            break;
        }
        int min1 = scoville[0];
        pop_heap(scoville.begin(), scoville.end(),greater<>{});
        scoville.pop_back(); 
        int min2 = scoville[0];
        pop_heap(scoville.begin(), scoville.end(),greater<>{});
        scoville.pop_back(); 

        int newint = min1 + (min2 * 2);

        scoville.push_back(newint);
        push_heap(scoville.begin(), scoville.end(),greater<>{});
        answer++;
    }

    return answer;
}

이건 예전에 풀었던 코드를 그대로 가져왔다.

내가 첫번째에 작성했던것과 차이가 없어보이는데,,

 

처음 찾은 차이점 : greater<>() vs greater<>{}

=> 근데 이건 문제가 아니었다. 그냥 c++11때 추가된 중괄호 초기화 문법이었고, 기능에 차이는 없다.

실제로 세번째코드의 {}를 ()로 바꿔서 실행했을때도 문제는 없었다.

 

두번째 찾은 차이점 : if(scovile.size() < 2)에서 처리의 차이

=> 그냥 return을 하는것과, answer를 바꾸고 break를 하는 차이였지만,,,

이것도 문제는 아니었다.

 

진짜 문제점 : make_heap vs push_heap

while문의 마지막부분에, 새로운 스코빌지수를 계산해서 heap에 넣어줄 때 차이가 있었고 이게 문제였다!

문제코드는 make_heap을 해주었고, 세번째코드는 push_heap을 해주었다,

 

https://en.cppreference.com/w/cpp/algorithm/push_heap

std::push_heap - cppreference.com

push_heap은 logn의 시간복잡도를 가진다 (make_heap이 n의 시간복잡도를 가지는것과 비교됨)

=> 즉 push_heap을 했어야 했다.

 

make_heap을 해주면 while전체의 시간복잡도는 n^2이 되는데

push_heap을 해주면 whle전체의 시간복잡도는 nlogn!!

 

그러니까 두번째에서 우선순위큐로 해결됐던것도, push_heap의 차이때문이었던것 같다

(queue vs heap 잘 구분하기!)

https://usowelcome.tistory.com/8

우선순위큐

https://usowelcome.tistory.com/4

힙(heap)

큐를 구현하는 방법이 힙인것! (따로 생각하지 말자^^...)

 

 

에휴 한번 풀어본문제였는데...^^;;;;;