STL Priority_queue(heap), (20190503)

1. Heap (=priority queue)

값이 들어가면 정렬된 형태로 저장하는 구조. 넣을때 logN, 뺄 때 logN의 시간이 걸린다.

priority_queue<int> pq;

pq.push()

pq.pop()

pq.top() => 특이하게 top을 쓴다

 

작은거부터 뽑고싶을 때는

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

혹은

priority_queue<int> pq;
그대로 해놓고 3을 넣지말고 -3을 넣고 뺄때 - 붙여주면 됨 ㅋㅋㅋㅋㅋ 신박하다

 

문제 : https://www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

코드 1 :

#include <queue>
#include <stdio.h>
using namespace std;
priority_queue<int> pq;
void f(int n){
	if(n<=0) return;
	int a=pq.top();
	pq.pop();
	f(n-1);
	printf("%d\n", a);
	return; 
}
int main(){
	int N;
	scanf("%d", &N);
	for(int i=0; i<N; ++i){
		int t;
		scanf("%d", &t);
		pq.push(t);
	}
	f(N);
	return 0;
}

 

코드 2 : 

#include <queue>
#include <stdio.h>
using namespace std;
priority_queue<int> pq;
int main(){
	int N;
	scanf("%d", &N);
	for(int i=0; i<N; ++i){
		int t;
		scanf("%d", &t);
		pq.push(-t);
	}
	for(int i=0; i<N; ++i){
		printf("%d\n", -pq.top());
		pq.pop();
	}
	return 0;
}

 

2. Set

집합. 중복 없이 데이터를 담는다.

표지판을 세워둔다고 생각을 하면 쉽다.

우선 end()라는 표지판을 세운다. 기본으로 들어가있으며 값은 여기에 들어가지 않는다. end()의 값을 출력하려들지 말자. 프로그램 터진다.

값을 넣을 때마다 그 값을 새겨둔 표지판을 하나 새로 세운다고 생각하자.

이미 세운 표지판과 같은 값이 들어오면 무시한다.

 

어떤 원소 A가 집합 S에 들어있는지 안들어있는지 logN의 시간으로 판단을 빠르게할 수 있다.

하지만 넣을때 logN, 뺄 때 logN이 걸린다.

 

find() 쓰는 법 : 

set<int> s;

if(s.find(3) != s.end()){ } //s 안에 3있어여~

 

혹은 set<int> ::iterator it = s.find(3);

문제 : https://www.acmicpc.net/problem/7785

7785번: 회사에 있는 사람

 

**set<int> ::iterator

자 iterator이 뭘까? iterator=반복의 뜻.

set<int> ::iterator는 셋 안에 있는 반복자?라고 생각하면 댐. for문같은 반복문 돌릴 때 사용하라고 준거.

어떻게 쓰면 좋을까?

for(set<int> ::iterator it = s.begin(); it!=s.end(); ++it) { } 이렇게 쓰면 댐.

셋의 시작부분부터 끝날때까지 iterator을 하나씩 증가시켜준다는 뜻. 일반적인 for문과 비슷하다. 부등호 대신에 !=가 들어갔다고 생각하자.

출력은 다음과 같이 할 수 있다.

cout << *it << '\n';

iterator은 포인터가 아니지만 보기 쉽게 하려고 *을 쓴거.

 

set을 iterator을 이용하여 돌려주면 오름차순 정렬된 값이 나온다.

set은 Balanced Binary Search Tree를 사용하며, 구현은 까다롭다고 한다.

 

 

 

3. map

기본적으로 set으로 이루어져있으므로 함수들은 set과 유사하다.

특징은 key와 value로 매칭이 된다는 것이다.

map<string, int>이런식으로 쓴다.

 

단어의 개수를 찾아볼까?

map<string, int> cnt;

for(){

    string str; cin >> str;

    cnt[str] ++;

}

이런식으로 셀 수 있다. 와우~

문제 : https://www.acmicpc.net/problem/10808

코드 : 

#include <stdio.h>
#include <iostream>
#include <map>
#include <string>
using namespace std;
map<char,int> m;
int main(){
	string s;
	cin >> s;
	for(int i=0; i<s.length(); ++i){
		m[s[i]]++;
	}
	for(int i=0; i<26; ++i){
		char c=i+'a';
		printf("%d ", m[c]);
	}
}

 

4. sort

#include <algorithm>에 들어있다.

int arr[1000]; 배열 arr이 있다.

sort(arr, arr+N); 이런식으로 하면 arr의 첫번째부터 N번째까지 오름차순 정렬을 한다. (포인터 연산)

 

문제(아까 풀었던거를 소트로 다시) : https://www.acmicpc.net/problem/2751

코드 : 

#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
vector<int> a;
int main(){
	int N;
	scanf("%d", &N);
	for(int i=0; i<N; ++i){
		int temp;
		scanf("%d", &temp);
		a.push_back(temp);
	}
	sort(a.begin(), a.end());
	for(int i=0; i<N; ++i){
		printf("%d\n", a[i]);
	}
}