1181 단어 정렬/11650 좌표 정렬하기/11651 좌표 정렬하기2/2750 수 정렬하기/10989 수 정렬하기3/10814 나이순 정렬
1. 1181 단어 정렬
https://www.acmicpc.net/problem/1181
1181번: 단어 정렬
첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.
www.acmicpc.net
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>
using namespace std;
int main() {
cin.tie(NULL);
cin.sync_with_stdio(false);
int n;
cin >> n;
string* arr = new string[n];
for (int i = 0; i < n; i++) {
string a;
cin >> a;
arr[i] = a;
}
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (arr[i].size() > arr[j].size()) {
string temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
else if (arr[i].length() == arr[j].length()) {
int idx = 0;
while (true) {
if (arr[i] == arr[j]) {
break;
}
if (arr[i][idx] == arr[j][idx]) {
idx++;
}
else if (arr[i][idx] > arr[j][idx]) {
string temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
break;
}
else {
break;
}
}
}
}
}
for (int s = 0; s < n; s++) {
if (s!=0&&arr[s - 1] == arr[s])
continue;
cout << arr[s] << "\n";
}
}처음에는 위코드로 구현하였다. vs에서 실행했을 때는 성공이었지만 백준에서의 결과는 시간초과였다. 시간복잡도가 O(N^2)이니 당연한 결과였다.
c++ STL의 sort 함수를 바킹독에서 공부하고 돌아왔다.
이후 짠 코드는 아래와 같다.
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>
using namespace std;
bool compare(string a, string b) {
if (a.length() == b.length())
return a < b;
return a.length() < b.length();
}
int main() {
cin.tie(NULL);
cin.sync_with_stdio(false);
int n;
cin >> n;
string* arr = new string[n];
for (int i = 0; i < n; i++) {
string a;
cin >> a;
arr[i] = a;
}
sort(arr, arr + n, compare);
for (int s = 0; s < n; s++) {
if (s != 0 && arr[s - 1] == arr[s])
continue;
cout << arr[s] << "\n";
}
}결과는 성공!
2.11650 좌표 정렬하기
https://www.acmicpc.net/problem/11650
11650번: 좌표 정렬하기
첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.
www.acmicpc.net
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>
#include<vector>
using namespace std;
vector<pair<int, int>>v;
int main() {
cin.tie(NULL);
cin.sync_with_stdio(false);
int n;
cin >> n;
int x, y;
for (int i = 0; i < n; i++) {
cin >> x >> y;
v.push_back({ x,y });
}
sort(v.begin(), v.end());
for (int i = 0; i < n; i++) {
cout << v[i].first << " " << v[i].second << "\n";
}
return 0;
}
3.11651 좌표 정렬하기2
https://www.acmicpc.net/problem/11651
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>
#include<vector>
using namespace std;
vector<pair<int, int>>v;
bool compare(pair<int,int> v1, pair<int,int> v2) {
if (v1.second == v2.second) {
return v1.first < v2.first;
}
return v1.second < v2.second;
}
int main() {
cin.tie(NULL);
cin.sync_with_stdio(false);
int n;
cin >> n;
int x, y;
for (int i = 0; i < n; i++) {
cin >> x >> y;
v.push_back({ x,y });
}
sort(v.begin(), v.end(),compare);
for (int i = 0; i < n; i++) {
cout << v[i].first << " " << v[i].second << "\n";
}
return 0;
}
4. 수 정렬하기
https://www.acmicpc.net/problem/2750
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>
#include<vector>
using namespace std;
int main() {
cin.tie(NULL);
cin.sync_with_stdio(false);
int n;
cin >> n;
vector<int> v;
for (int i = 0; i < n; i++) {
int a;
cin >> a;
v.push_back(a);
}
sort(v.begin(), v.end());
for (auto v1: v) {
cout << v1<<"\n";
}
}
5.10989 수 정렬하기 3
https://www.acmicpc.net/problem/10989
10989번: 수 정렬하기 3
첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.
www.acmicpc.net
메모리 초과가 나서 counting sort 알고리즘을 사용해야 했다.
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
int arr[10001];
int main() {
cin.tie(NULL);
cin.sync_with_stdio(false);
cout.tie(NULL);
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int a;
cin >> a;
arr[a] += 1;
}
for (int i = 1; i < 10001; i++) {
for (int j = 0; j < arr[i]; j++) {
cout << i << "\n";
}
}
}
6.10814 나이순 정렬
https://www.acmicpc.net/problem/10814
10814번: 나이순 정렬
온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을
www.acmicpc.net
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
bool compare(pair<int, string>a1, pair<int, string>a2) {
return a1.first < a2.first;
}
int main() {
cin.tie(NULL);
cin.sync_with_stdio(false);
cout.tie(NULL);
int n;
cin >> n;
vector<pair<int, string>>v;
for (int i = 0; i < n; i++) {
int age;
string name;
cin >> age >> name;
pair<int, string>a = { age,name };
v.push_back(a);
}
stable_sort(v.begin(), v.end(),compare);
for (int i = 0; i < v.size(); i++) {
cout << v[i].first << " " << v[i].second << "\n";
}
}vetor에 넣은 순서를 보존해주기 위해서 stable_sort를 사용해야하는 문제였다.