[BOJ] C++ 11650 "좌표 정렬하기" 문제 풀이 _ nov

#INFO

난이도 : SILVER5

문제 유형 : 정렬

출처 : 11650번: 좌표 정렬하기 (acmicpc.net)

---

#SOLVE

시간복잡도를 생각하지 않고 무작정 구현했더니, 시간초과가 발생했다.

아래는 모든 원소를 차례로 비교하는 방식의 알고리즘인데, 이는 n의 값이 100,000이 되었을 때 거의 100초에 달하는 시간이 걸리게된다.

#include <bits/stdc++.h>
using namespace std;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int n;
  cin >> n;
  vector<pair<int, int>> xy;
  xy.resize(n);
  for(int i = 0; i < n; ++i){
    cin >> xy[i].first >> xy[i].second;
  }
  for(int i = 0; i < n; ++i){
    for(int j = i + 1; j < n; ++j){
      if(xy[i].first > xy[j].first){
        iter_swap(xy.begin() + i, xy.begin() + j);
      } 
      else if((xy[i].first == xy[j].first) &&
        (xy[i].second > xy[j].second)){
        iter_swap(xy.begin() + i, xy.begin() + j);
        }
    }
  }

  for(int i = 0; i < n; ++i){
    cout << xy[i].first << " " << xy[i].second << '\n';
  }
  return 0;
}

 

해결방법은 간단하다. C++ STL <algorithm> 헤더에 정의된 sort 정렬함수를 사용하면 된다.

sort 함수는 quick sort 기반 알고리즘으로 제작된 intro sort 알고리즘을 사용하는데, 항상 O(nlogn)의 시간복잡도를 보장한다.

_ About sort

#include <bits/stdc++.h>
using namespace std;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int n;
  cin >> n;
  vector<pair<int, int>> xy;
  xy.resize(n);
  for(int i = 0; i < n; ++i){
    cin >> xy[i].first >> xy[i].second;
  }
  sort(xy.begin(), xy.end());
  for(int i = 0; i < n; ++i){
    cout << xy[i].first << " " << xy[i].second << '\n';
  }
  return 0;
}