[C++][BOJ-정렬 문제들(2751 11650 11651 10814 10989 11652)] stable_sort, vector pair 정렬, 메모리 계산, map,int 범위 ,

[BOJ 2751]

#include <bits/stdc++.h>

using namespace std;

int main(){
	int n,*arr;
	scanf("%d",&n);
	arr = new int [n];
	for(int i=0;i<n;i++) scanf("%d",&arr[i]);
	sort(arr,arr+n);
	for(int i = 0 ; i <n; i++) printf("%d\n",arr[i]);
	return 0;
}

 

 

 

[BOJ 11650]

#include <bits/stdc++.h>

using namespace std;
//compare 없이도 pair 오름차순 정렬됨 
//bool compare(pair<int,int> a, pair<int,int> b){
//	return (a.first == b.first) ? (a.second < b.second ):( a.first < b.first);
//}

int main(){
	int n;
	scanf("%d",&n);
	vector< pair<int,int> > v(n);
	v.clear();	
	while(n--){
		int a,b;
		scanf("%d %d",&a,&b);
		v.push_back( {a,b} );//make_pair(a,b)
	}
	sort(v.begin(),v.end());
	for(auto elem : v)	
		printf("%d %d\n",  elem.first , elem.second);	
	return 0;
}

 

주의점

 

1. 여기선 sort 정렬 조건에 first가 같을 때 second 기준으로 정렬하는 코드 주석처리해도 맞았지만,

이 정렬 조건 안주면 sort 결과가 first 기준 정렬 후 sec는 unstable하게(꼭 sec 크기 순으로 정렬해서 나오는게 아님, 입력된 순서 유지해주는 것도 아님) 나온다고 한다.

 

2. vector 사용

vector<int> v(n);
// 0으로 초기화된 n개 원소가진 벡터 v 생성

vector <int> v(n,3);
//3으로 초기화된

vector<int> v[n];
// n개 원소가진 벡터 v 생성

헷갈리지말고

 

 

3.

make_pair(a,b) 대신 {a,b} 도 가능

for(auto elem : v) 대신 for(auto [a,b] : v ) 이렇게도 사용하던데 나는 오류난ㄷ.

 

 

[BOJ 11651]

#include <bits/stdc++.h>

using namespace std;
//compare를 이용해도 되지만  a,b를 바꿔서 vector에 넣어주면 되겠지 
//bool compare(pair<int,int> a, pair<int,int> b){
//	return (a.second == b.second) ? (a.first<b.first):(a.second < b.second);
//}
int main(){
	int n;
	scanf("%d",&n);
	
	vector <pair<int,int>> v(n); v.clear();
	
	while(n--){
		int a,b;
		scanf("%d %d",&a,&b);
		v.push_back({b,a});
	}
	sort(v.begin(),v.end(),compare);
	for(auto e : v) printf("%d %d\n",e.second,e.first);
	return 0;
}

문제가 first 말고 sec 기준 정렬이었다.

센스있게 first와 sec 자리 바꿔서 넣어준 후 출력할 때 제대로 해주면 더 쉽다.

 

 

[BOJ 10814]

#include <bits/stdc++.h>

using namespace std;
bool compare(pair<int, string> a, pair<int, string> b){
    return a.first<b.first;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int n;
	cin>>n;
	vector<pair<int,string>> v(n); v.clear();
	
	while(n--){
		int a;string b;	
		cin>>a>>b;
		v.push_back(make_pair(a,b));
	}
	
	stable_sort(v.begin(),v.end(),compare);
	//sort와 다르게 구조체처럼 여러 값들이 묶여 있을 때 하나의 요소로 정렬 했을 때
	// 다른 요소들의 정렬 순서도 정렬 전과 같이 그대로 유지될 수 있게 해줌  
	for(auto e : v) cout<<e.first<<" "<<e.second<<"\n";
	return 0;
} 

문제 좀 제대로 읽고 풀자. 그 전에 푼 문제겠지라고 생각하고 안읽지말고.... 

 

1. sort (quick sort )vs stable_sort (merge sort)

- sort 가 stable sort 보다 조금 더 빠르다.

- stable_sort : table_sort 동일한 정렬 기준 가진 순서가 정렬 이후에도 유지 , merge sort, insert sort

    - ex pair에서 first가지고 정렬하면 first가 같은 경우엔 원래 배열에 있던 순서대로 유지해주나봐

- sort의 경우엔 위의 pair 예시에서 그 순서를 유지할지 안할지 불확실(unstable) , quick sort 

 

2. ios::sync_with_stdio(false)

cin.tie(NULL) ;  cout.tie(NULL);

cin,cout만 쓰는 경우 이거 써주자..

 

3. scanf, printf 에서 string 입출력 좀 ......별로야....다시 찾아보자

 

 

 

[BOJ 10989]

#include <bits/stdc++.h> 
using namespace std;
int main(){
	int n,tmp, arr[10001]={0,};
	scanf("%d",&n);
	while(n--){
		scanf("%d",&tmp);
		arr[tmp]++;
	}
	for(int i = 1 ; i<10001;i++) while(arr[i]--) printf("%d\n",i);
	return 0;
}

문제의 조건을 보면 메모리 제한이 8MB이다.

수 정렬을 위해 기존의 하던대로 N사이즈(10,000,000) 만큼의 배열을 만들면 메모리 초과가 뜬다.

int 10,000,000 배열 -> 40mb가 됨.

근데 문제를 읽어보면 입력되는 수가 10,000이하 자연수다.

10,000 짜리 배열을 만들어서 갯수를 세자. 그럼 끝.

(프로그래머스에서 비슷한 문제 풀었던 것 같음)

 

[작성한 코드 메모리 확인하기]

int   32bits  4byte

int 형 배열 5,000*5,000개 = 25,000,000개 선언 시

25,000,000 * 4 = 100,000,000 byte 사용.

100,000,000 / 1024 = 97656.25 KB

97656.25 KB / 1024 = 대략 95 MB

 

long long , double 64bits 8byte 이므로 int의 2배

 

 

[BOJ 11652]

#include <bits/stdc++.h>

using namespace std;

int main(){
	int N,max=1;
	long long *a,ans;
	scanf("%d",&N);
	a = new long long[N];
	for(int i = 0 ; i< N ; i++)	scanf("%lld",&a[i]);
	sort(a,a+N);

	ans = a[0];
	for(int i = 1,tmp=1 ; i<N;i++){
		if(a[i-1] == a[i]){
			if( ++tmp > max){
				ans = a[i];
				max = tmp;
			}	
		}
		else{
			tmp=1;
		}
		
	}
	printf("%lld",ans);
	return 0;
}

수 범위가 int를 벗어나니까 long long 사용

int는 대략 2^31 

입력되는 개수가 몇개 없으니까 다 입력 받은 후 크기 순 정렬하고

제일 개수 많고 그 중에서 가장 작은 수 출력.

 

다른 풀이

#include <bits/stdc++.h>

using namespace std;

int main(){
	int N,max=0;
	long long tmp;
	scanf("%d",&N);
	map <long long ,int> m;	
	while(N--){
		scanf("%lld", &tmp ),m[tmp]++;
	}	
	for(auto e : m){
		if(max < e.second) max = e.second, tmp = e.first;
	}
	printf("%lld",tmp);
	return 0;
}

봐야할 점

1. map<long long, int> 이용.

map은 자동으로 정렬되니까, 그리고 scanf 받아들여서 map에 find 안하고 바로 m[ tmp ] ++; 함.

 

2. 위의 풀이와 조금 다르게 map으로 나온 횟수를 체크하니까

하단 for문에서 바로 max으로 초기화 한 후 바로 비교할 수 있으니까 i == 0 일때 뭐 고민할 필요가 없어지네 

 

3.  한 줄에 ,로 그냥 써버리네

 

 

[BOJ 11650]

 

int 범위 대략 ± 2,000,000,000 기억 좀, 2^31 하고

 

 

 

[BOJ 11650]

 

[BOJ 11650]

 

 

 

 

 

 

참고 사이트

sort vs stable_sort

vector 사용법

vector 생성법

sort vs stable sort2