정렬은 O(logN)이 걸리는 정렬을 사용한다. 정렬의 경우 직접 구현하는 것보다, STL을 사용하는 것이 좋다.
pair 배열을 정렬하는 경우 : 자동으로 left를 기준으로, left가 동일하다면 right를 기준으로 정렬된다.
struct 배열을 정렬하는 경우 : cmp 함수를 만들어서 비교자를 sort 함수에 넣어준다.
struct Point {
int x, y;
}
// u가 앞에 있고, v가 뒤에 있는 것
bool cmp(const Point &u, const Point &v){
if(u.x < v.x) // u v 의 순서가 올바른 경우
return true;
else if (u.x == v.x)
return u.y < v.y;
else // u v 의 순서가 올바르지 않은 경우
return false;
}
위 코드는, 정렬된 배열에서 u가 v보다 앞에 있는게 옳다면 true를 반환하고, 그렇지 않다면 false를 반환한다. 따라서 x를 기준으로 오름차순 정렬하는 비교자이다.
greater, less 템플릿 사용하기
sort(v.begin(), v.end(), greater<int>()); // 내림차순 정렬
sort(v.begin(), v.end(), less<int>()); // 오름차순 정렬
#include <iostream>
#include <vector>
#include <algorithm>
#define endl '\\n'
using namespace std;
struct Point {
int x, y;
};
bool cmp(const Point& u, const Point& v) {
if (u.y == v.y) return u.x < v.x;
else return u.y < v.y;
}
int main() {
ios_base::sync_with_stdio(false);
cout.tie(NULL); cin.tie(NULL);
int n; cin >> n;
vector<Point> v(n);
for (int i = 0; i < n; i++)
cin >> v[i].x >> v[i].y;
sort(v.begin(), v.end(), cmp);
for (int i = 0; i < n; i++)
cout << v[i].x << " " << v[i].y << endl;
return 0;
}
값이 같은 것이 있는 배열에 대해서, 정렬 후 그 순서가 유지되는 정렬 알고리즘이다. MergeSort, Bubble Sort 등이 있다.
STL에서는 stable_sort 알고리즘으로 사용하고, Stable Sorting이 아닌 알고리즘의 경우 순서를 나타내는 변수를 하나 더 저장해서 순서를 유지하도록 구현한다.
#include <iostream>
#include <vector>
#include <algorithm>
#define endl '\\n'
using namespace std;
struct Person {
int age;
string name;
};
bool cmp(const Person& u, const Person& v) {
return u.age < v.age;
}
int main() {
ios_base::sync_with_stdio(false);
cout.tie(NULL); cin.tie(NULL);
int n; cin >> n;
vector<Person> persons(n);
for (int i = 0; i < n; i++)
cin >> persons[i].age >> persons[i].name;
stable_sort(persons.begin(), persons.end(), cmp);
for (int i = 0; i < n; i++)
cout << persons[i].age << " " << persons[i].name << endl;
return 0;
}
#include <iostream>
#include <vector>
#include <algorithm>
#define endl '\\n'
using namespace std;
struct Subject {
string name;
int korea, english, math;
};
bool cmp(const Subject& u, const Subject& v) {
if (u.korea == v.korea) {
if (u.english == v.english) {
if (u.math == v.math)
return u.name < v.name;
return u.math > v.math;
}
return u.english < v.english;
}
else
return u.korea > v.korea;
}
int main() {
ios_base::sync_with_stdio(false);
cout.tie(NULL); cin.tie(NULL);
int n; cin >> n;
vector<Subject> scores(n);
for (int i = 0; i < n; i++)
cin >> scores[i].name >> scores[i].korea >> scores[i].english >> scores[i].math;
sort(scores.begin(), scores.end(), cmp);
for (int i = 0; i < n; i++)
cout << scores[i].name << endl;
return 0;
}
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define endl '\\n'
using namespace std;
int check[10001];
int main() {
ios_base::sync_with_stdio(false);
cout.tie(NULL); cin.tie(NULL);
memset(check, sizeof(check), 0);
int n; cin >> n;
for (int i = 0; i < n; i++) {
int num; cin >> num;
check[num]++;
}
for (int i = 0; i < 10001; i++)
while (check[i] != 0) {
cout << i << endl;
check[i]--;
}
return 0;
}
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cout.tie(NULL); cin.tie(NULL);
int n; cin >> n;
vector<long long> numbers(n);
for (int i = 0; i < n; i++)
cin >> numbers[i];
sort(numbers.begin(), numbers.end());
int max_value = 0;
vector<long long>::iterator iter = numbers.begin();
int ret = *iter;
while (true) {
vector<long long>::iterator lower, upper;
lower = lower_bound(numbers.begin(), numbers.end(), *iter);
upper = upper_bound(numbers.begin(), numbers.end(), *iter);
int cand = (upper - numbers.begin()) - (lower - numbers.begin());
if (cand > max_value) {
max_value = cand;
ret = *lower;
}
if (upper >= numbers.end()) break;
else iter = upper;
}
cout << ret << endl;
return 0;
}
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool cmp(const pair<long long, int>& u, const pair<long long, int>& v) {
if (u.second == v.second) return u.first < v.first;
else return u.second > v.second;
}
int main() {
ios_base::sync_with_stdio(false);
cout.tie(NULL); cin.tie(NULL);
int n; cin >> n;
vector<long long> num(n);
for (int i = 0; i < n; i++)
cin >> num[i];
sort(num.begin(), num.end());
int cnt = 1;
int max = 0;
long long ret = 0;
long long prev = num[0];
for (int index = 1; index < n; index++) {
if(prev != num[index]) {
if (cnt > max){
max = cnt;
ret = prev;
}
cnt = 1;
}
else
cnt++;
prev = num[index];
}
**if (cnt > max) ret = prev;**
cout << ret << endl;
return 0;
}
10 1 2 2 3 3 4 4 4 4 4
와 같은 테스트 케이스 처럼, 마지막에 최대 갯수의 숫자가 나왔을 때 for문에서 if(cnt > max) 가 호출되지 않는다. 따라서 for문이 종료되면 if(cnt > max) ret = prev 코드를 하나 더 추가해준다.
2^62와 같은 수에 겁먹고 다르게 풀어야 하나 싶었는데, 그냥 단순한 방법으로 풀고 배열의 타입만 long long으로 해주면 되는 것이었다. 겁 먹지 말자 !
해설
정렬한 이후 문제를 풀게 되면 O(N), 한 번의 탐색으로 문제를 풀 수 있다. 정렬에 NlogN이 들기 때문에 최종적으로 O(NlogN)의 시간 복잡도가 걸린다.
버블 정렬은 큰 수를 차례대로 뒤에 보내는 과정을 반복한다. 이 문제에서 더 이상 배열이 변하지 않을 때 이 과정을 몇 번 반복했는 지(i)를 출력하고 있다.
1 10 5 2 3 를 예시로 들면, 10을 맨 뒤로 보내기 때문에 i = 1일 때 배열은 1 5 2 3 10으로 바뀐다. 5를 맨 뒤로 보내기 때문에 i = 2일 때 배열은 1 2 3 5 10 으로 바뀐다. 그 다음은 더 이상 보낼 배열이 없기 때문에 i = 3인 값이 출력된다.
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
int check[1000001]; // check[i] : i 숫자가 몇 번 나오는 지 검사
int main() {
int N; cin >> N;
vector<int> A(N + 1);
memset(check, sizeof(check), 0);
for (int i = 1; i <= N; i++) {
int x; cin >> x;
A[i] = x;
check[x]++;
}
int cnt = 0;
while (true) {
int i;
for (i = 1; i <= N; i++) {
if (check[A[i]] == 0 || check[A[i+1]] == 0) continue;
if (A[i] > A[i + 1]) {
cnt++;
check[A[i]]--;
break;
}
}
if (i == N + 1) break;
}
cout << cnt + 1 << endl;
return 0;
}
가장 큰 수 하나를 뺄 때마다 erase를 사용하면 N이라는 시간이 들기 때문에 비효율적이라고 생각하였다. 따라서 check 배열을 사용해 이미 사용한 숫자가 나오면 continue하려고 했는데, 그렇게 구현하면 1 10 5 2 3에서 10을 빼서 if(A[i] > A[i + 1] 구문에서 1과 5를 연결짓는 것이 불가능하였다.
그래서 인덱스로 접근해서 방문한 인덱스면 제거하였음을 저장하는 removed 배열과 next_index 를 pair로 저장하여 다음 비교할 숫자를 지정하도록 하였다.
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
bool removed[500001];
int main() {
int N; cin >> N;
// number, next_index
vector<pair<int,int>> A(N + 1);
memset(removed, sizeof(removed), false);
for (int i = 1; i <= N; i++) {
int x; cin >> x;
A[i].first = x;
if (i == N) A[i].second = -1;
else
A[i].second = i + 1;
}
int cnt = 0;
while (true) {
int i;
for (i = 1; i <= N; i++) {
if (removed[i]) continue;
int next_index = A[i].second;
if (next_index == -1) continue;
if (A[i].first > A[next_index].first) {
cnt++;
removed[i] = true;
if (i == 1) break;
else if (i == N) A[i].second = -1;
else
A[i - 1].second = i + 1;
break;
}
}
if (i == N + 1)
break;
}
cout << cnt + 1 << endl;
return 0;
}
아쉽게도 시간초과가 나왔다. 결국에는 이 코드도 이중 for문으로 버블소트와 유사한 방식으로 해결하고 있기 때문에 시간복잡도는 똑같다는 것 같다.
해설
해설에서는 큰 숫자가 이동한다는 사실에 주목하지 않고, 큰 숫자가 뒤로 이동하면 작은 숫자가 최대 한 칸씩 앞으로 이동한다는 사실에 주목하였다.
따라서 정렬 후 어떤 숫자의 인덱스와, 정렬 전 그 숫자의 인덱스의 차이 중 가장 큰 것을 찾으면, 그게 정렬을 위해 큰 숫자가 이동한 횟수와 일치하게 되는 것이다. (개 천재)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int N; cin >> N;
vector<pair<int,int>> A(N);
for (int i = 0; i < N; i++) {
cin >> A[i].first;
A[i].second = i; // 정렬 전 위치 저장
}
sort(A.begin(), A.end());
int ret = 0;
for (int i = 0; i < N; i++) {
int cand = A[i].second - i;
if (cand > ret) ret = cand;
}
cout << ret + 1<< endl;
return 0;
}
시간복잡도는 O(NlogN)이다.