[BOJ step 14] 정렬 1 ~ 6

3 분 소요

정렬(Sorting)

$O(n^2)$

$O(n \log n)$

참조 : 위키백과

수 정렬하기

선택정렬을 이용한 풀이

#include<iostream>
#include<algorithm>
#include<vector>
#define endl '\n'
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int n; cin >> n;
	vector<int> v(n);
	for (int i = 0; i < n; i++)
		cin >> v[i];
	for (int i = 0; i < n; i++) {
		int m_idx = i;
		for (int j = i + 1; j < n; j++) 
			if (v[j] < v[m_idx]) m_idx = j;
		int tmp = v[m_idx];
		v[m_idx] = v[i];
		v[i] = tmp;
	}
	
	bool chk = false;
	for (int i = 0; i < v.size(); i++) {	
		if (!chk) {
			chk = true;
			cout << v[i] << endl;
		}
		else {
			if (v[i - 1] != v[i])chk = false;
			if (!chk) {
				chk = true;
				cout << v[i] << endl;
			}
		}
	}
	return 0;
}

수 정렬하기 2

C++ <algorithm> 에 있는 sort() 함수 역시 merge sort 기반으로 알고있다. 직접 구현한 코드를 이용한 풀이이다.

#include<cstdio>
int D[1000000];
int Tmp[1000000];
void MergeSort(int start, int end, int *data) {
	int i = start;
	int k = start;
	int m = (start + end) / 2;
	int j = m + 1;
	if (start >= end)return;	// 더 이상 분할할수없음.
	MergeSort(start, m, data);	// 쪼개기 왼쪽
	MergeSort(m + 1, end, data);// 쪼개기 오른쪽
	while ((i <= m) && (j <= end)) {	// 비교 후 정렬
		if (data[i] < data[j])Tmp[k++] = data[i++];
		else Tmp[k++] = data[j++];
	}
	while (i <= m)Tmp[k++] = data[i++];	// 남은 부분 정렬
	while (j <= end)Tmp[k++] = data[j++];
	for (i = start; i <= end; i++)data[i] = Tmp[i];	// 교환
}
int main() {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)scanf("%d", &D[i]);
	MergeSort(0, n - 1, D);
	for (int i = 0; i < n; i++)printf("%d\n", D[i]);
	return 0;
}

수 정렬하기 3

카운팅 정렬을 이용한 풀이

적은 범위가 주어진다면 범위만큼의 배열을 만들어 배열 인덱스를 수로 활용한다.

#include<cstdio>
int D[10001];
int main() {
	int n, a;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a);
		D[a]++;
	}
	for (int i = 0; i < 10001; i++) {
		for (int j = 0; j < D[i]; j++) {
			printf("%d\n", i);
		}
	}
	return 0;
}

통계학

위의 정렬방법들을 이용하여 풀이

#include<cstdio>
#include<algorithm>
using namespace std;
int Num[500000];
int Tmp[500000];
int Cnt[8001];
int Max;
int main() {
	int n, sum = 0;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &Num[i]);
		sum += Num[i];
		Cnt[Num[i] + 4000]++;
		if (Max < Cnt[Num[i] + 4000])Max = Cnt[Num[i] + 4000];
	}
	sort(Num, Num + n);
	int j = 0, frq;
	for (int i = 0; i < 8001; i++) {
		if (Cnt[i] == Max) {
			frq = i - 4000;
			j++;
			if (j == 2) {
				frq = i - 4000;
				break;
			}
		}
	}
	printf("%.0f\n", sum / (double)n);
	printf("%d\n", Num[n / 2]);
	printf("%d\n", frq);
	printf("%d\n", Num[n - 1] - Num[0]);
	return 0;
}

소트인사이드

string 정렬을 이용한 역순 출력

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

bool comp(char a, char b) { return a > b; }
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	string s;
	cin >> s;
	sort(s.begin(), s.end(), comp);
	cout << s;
	return 0;
}

좌표정렬하기

sort함수와 우선순위 큐를 이용한 풀이

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#define PII pair<int, int>
#define endl '\n'

using namespace std;

typedef struct pos {
	int x, y;
}Pos;
bool operator<(const Pos &a, const Pos &b) {
	if (a.x != b.x)return a.x > b.x;
	else return a.y > b.y;
}
priority_queue<Pos> pq;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	vector<PII> v;
	int n; cin >> n;
	while (n--) {
		int x, y;
		cin >> x >> y;
		v.push_back({ x,y });
	}
	sort(v.begin(), v.end());
	for (PII ans : v) {
		cout << ans.first << " " << ans.second << endl;
	}
	return 0;
}
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#define PII pair<int, int>
#define endl '\n'

using namespace std;

typedef struct pos {
	int x, y;
}Pos;
bool operator<(const Pos &a, const Pos &b) {
	if (a.x != b.x)return a.x > b.x;
	else return a.y > b.y;
}
priority_queue<Pos> pq;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n; cin >> n;
	while (n--) {
		Pos tmp;
		cin >> tmp.x >> tmp.y;
		pq.push(tmp);
	}
	while (!pq.empty()) {
		Pos cur = pq.top();
		pq.pop();
		cout << cur.x << " " << cur.y << endl;
	}
	return 0;
}

댓글남기기