4주차 과제(cpp)

min heap, max_heap  (우선순위 힙정렬)

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

#include <string>
#include <vector>
#include <queue>
#include<algorithm>
using namespace std;

/*
모든값이 0인데 K값이 1이상인경우 답이 없음  -1
-> vector의 가장 큰값과 낮은 값 모두 0인경우 -1로 리턴
더이상 더할게 없는 경우, K미만이면서 그러면 -1
*/
typedef long long ll;
int solution(vector<int> scoville, int K) {
    int answer = 0;
    priority_queue<ll, vector<ll>, greater<ll>>min_heap;
    for (int x = 0; x < scoville.size(); ++x) {
        min_heap.push(scoville[x]);
    }

    auto max_val = max_element(scoville.begin(), scoville.end());
    if (*max_val == 0 && min_heap.top() == 0 && K != 0)return -1;

    while (!min_heap.empty()) {
        if (min_heap.size() == 1 && min_heap.top() < K) return -1;
        ll a = min_heap.top();
        min_heap.pop();
        ll b = min_heap.top();
        min_heap.pop();
        if (a >= K && b >= K) break;
        min_heap.push(a + (b * 2));
        answer++;
    }
    return answer;
}

피드백: typedef 보다 using ll 즉 using 사용

    if (*max_val == 0 && min_heap.top() == 0 && K != 0)return -1;
    이건 min_heap.top() 보다 *min_val로 통일하는게 좋아보임

 

 

 

결과 : 

정확성: 80.8

효율성: 19.2

합계: 100.0 / 100.0

정확성 80.8은 뭔가요? 

총 100점 중 80.8 이고 효율성이 19.2 라는 뜻. 

효율성이 더 높아질 수 있나? 그럼 정확성은 낮아지나?    ㄴㄴ 정해놓은 효율성 점수와 정확성 점수가 있음.

프로그래머스 점수 

auto max_val =  max_element(scoville.begin(),scoville.end());
    if(*max_val == 0 && min_heap.top() == 0 && K!=0)return -1;

algorithm 헤더 불러와서 위 코드 대체해도 동일 성능.

 

min_heap에 값 넣는것도 복잡도에 영향가기에, 원본 그대로 해봐야함.

벡터에 작은 값 을 갖는 인덱스를 pop하는 기능있나?

lower_bound, upper_bound 이용해서 해볼려함.,

 

[벡터만 활용한다면,  stl min 함수 사용해서 min값찾고 +  min값 인덱스  이진탐색 + 해당 인덱스 지우기  이 컨셉을 루프안에서 2번하여 작은값과 그 다음 작은값 구해보기]

 

https://school.programmers.co.kr/courses/15280/lessons/130625

프로그래머스

#include<algorithm>
#include<iostream>
#include<string>
using namespace std;

int main(void) {
	string str = "xyb";
	int  a = 0;
	int b;
	int size_t = str.size();
	string result;
	while (a < size_t) { // a 가 string 사이즈 이상일 시 루프 빠져나옴 
		auto max_ch = max_element(str.begin()+a, str.end());
		if (*max_ch == 0) { // 범위 초과하면 널값이 나옴. (안전장치)
			break;
		}
		b =str.find(*max_ch, a);
		if (b == -1) break;
		result += *max_ch;
		a = b+1;
	}
	cout << result << endl;
}

참고하기 (시간복잡도)

https://d2.naver.com/helloworld/0315536

---

 

2번 시간초과

 

모범답안(feat 멘토님 코드 기반)

1. 

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

using namespace std;


string run(string s)
{
    string result;
	result.reserve(s.size());
    vector<vector<int>> vect(26);  // 2차원 벡터, 멀티 해시 directed address table 처럼.

	for(int x = 0; x < s.size(); ++x)
	{
		vect[s[x] -'a'].push_back(x);  // 문자 인덱스에 순서를 넣기

	}
	int lastIdx = -1;
	for ( int x = 25; x>=0; --x) // 결과 문자열 순서는 사전순으로 큰 문자부터 시작. 그러기에 역순으로 진행(z부터)
	{
		auto iter = lower_bound(vect[x].begin(), vect[x].end(), lastIdx); // lower_bound는 이진탐색으로 lastIdx 보다 높은 값 ( 순서 찾기)
		//처음 알파벳 인덱스의 순서값중 가장 낮은 순서값을 찾게 된다. 그리고 하기처럼 해당되는 동일 알파벳을 Push.   해당 알파벳 이전의 알파벳들은 나가리 된다. (왜? 사전순으로 큰 알파벳부터 시작하기에)
		for(;iter!=vect[x].end(); ++iter)  
		{
			result.push_back('a' + x);
			lastIdx = *iter;
		}
	}
	return result;
}

int main(void)
{
	string rt = run("wgezxcas");
	cout << rt<< endl;
}

 

 

2. stack 활용