BOJ 11651번 좌표 정렬하기2

BOJ : https://www.acmicpc.net/problem/11651

 

 

2개의 소스로 시간을 비교해보았다.

학교 알고리즘 과제를 할때 정렬이 필요한 경우 compare 함수를 만들어서 사용했던 경험이 많은데

이 경우와 변수 위치를 조금 바꾸어 compare 함수 없이 정렬을 했을 때 

시간복잡도가 큰 문제의 경우 compare 함수를 만들어서 문제를 푼 경우가 시간이 더욱 오래걸렸었다.

 

소스1. compare 함수 사용

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
pair<int, int> pii[100001];
 
bool cmp(pair<int, int>& a, pair<int, int>& b) {
    if (a.second != b.second) return a.second < b.second;
    else return a.first < b.first;
}
 
int main() {
    int N; cin >> N;
    for (int i = 0; i < N; i++) cin >> pii[i].first >> pii[i].second;
 
    sort(pii, pii + N, cmp);
    for (int i = 0; i < N; i++) cout << pii[i].first << ' ' << pii[i].second << '\n';
    return 0;
}

 

소스2. 기본 STL sort 사용

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
pair<int, int> pii[100001];
 
int main() {
    int N; cin >> N;
    for (int i = 0; i < N; i++) cin >> pii[i].second >> pii[i].first;
 
    sort(pii, pii + N);
    for (int i = 0; i < N; i++) cout << pii[i].second << ' ' << pii[i].first << '\n';
    return 0;
}

 

6분전이라 적힌 AC 가 compare 함수를 사용한 예제이다.

겨우 10만 케이스인데도 시간차이가 보인다면

학교과제할때 크게 느꼈던 천만~ 같은 경우 compare 함수를 사용하는 것은 다시 한번 생각해볼만 한 것 같다.