[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]
참고 사이트