BOJ 11650, 좌표 정렬하기

문제

2차원 평면 위의 점 N개가 주어진다. 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.

출력

첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다.

내 접근

1. 좌표 두 개 관리하는 클래스 Pos를 만들어야겠다
2. std::vector<Pos> 에서 보관하고 std::sort 로 정렬하자
3. std::sort 메서드의 비교 함수를 커스텀해야겠다

구현

#include <iostream>
#define IO std::cin.tie(NULL), std::ios_base::sync_with_stdio(false)
#include <algorithm>
#include <vector>

class Pos {
public:
  int x, y;
  Pos(int x, int y);
  void show() { std::cout << x << " " << y << '\n'; };
};
Pos::Pos(int x, int y) : x(x), y(y) {}

bool comp(Pos p1, Pos p2) {
  if (p1.x == p2.x)
    return p1.y < p2.y;
  return p1.x < p2.x;
}

void solve() {
  int n;
  std::cin >> n;

  std::vector<Pos> v;

  int x, y;
  for (int i = 0; i < n; i++) {
    std::cin >> x >> y;
    v.push_back(Pos(x, y));
  }

  std::sort(v.begin(), v.end(), comp);

  for (int i = 0; i < n; i++) {
    v[i].show();
  }
}

int main() {
  IO;
  solve();
  return 0;
}

개선점

비교 함수 전달 방식

bool comp(Pos p1, Pos p2)

정렬 중 비교가 일어날 때마다 객체 복사가 일어남.

bool comp(const Pos& p1, const Pos& p2) {
	if (p1.x == p2.x) return p1.y < p2.y;
	return p1.x < p2.x;
}

관습적으로는 참조 전달을 하는게 좋을 것.

굳이 클래스일 이유?

Pos 클래스는

• 데이터 묶음
• 특별히 유지하는 불변식 없음
• 상속 없음

데이터 저장이 목적이면 struct 를 사용하는게 더 자연스러움

struct Pos {
	int x, y;
}

값을 튜플처럼 다루고 싶었는데, std::pair 가 있었음

std::vector<std::pair<int, int>> v(n);

std::pair 는 기본 비교 연산부터 내가 구현했던 규칙을 제공함

벡터를 미리 할당하자

n을 이미 알고 있는 구조니까, std::vector 의 크기를 미리 정해서 메모리 재할당을 최소화하자 `

std::vector<Pos> n;
v.reserve(n);

또는

std::vector<Pos> v(n);
for (int i = 0; i < n; i++) {
	std::cin >> v[i].x >> v[i].y;
}