백준 11651 번 문제 풀이 C++ :좌표 정렬하기 2

#81. 백준 11651번 문제 풀이: 좌표 정렬하기 2

2차원 평면 위의 점 N개가 주어진다. 좌표를 y좌표가 증가하는 순으로, y좌표가 같으면 x좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오. 입력: 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000≤xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. 출력: 첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다.

입력/출력

--입력--
5
0 4
1 2
1 -1
2 2
3 3
--출력--
1 -1
1 2
2 2
3 3
0 4

문제풀이+해설

좌표와 같은 2차원 배열형태의 배열을 소팅하는 문제이다.
언어에 따라 2차원 배열 소팅하는 기능을 기본적으로 제공하는 언어가 있고, 그렇치 않은 언어들이 있다.C++ 에서는 sort 함수를 사용하면 이중배열도 첫번째 항목 우선, 같으면 다음 항목 우선으로 정렬해 줍니다.
여기서는 첫번째 항목이 아닌 y(두번째 항목)로 우선 소팅을 해야 하니 별도로 비교함수 compare 함수를 작성합니다.

code sol.

코드편집/실행

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool compare(pair<int, int>a, pair<int, int>b) {
  if(a.second == b.second) {
    return a.first < b.first; // y(second)값이 같으면 x(first)값 비교
  } else {
    return a.second < b.second; // y(second)값 우선 순위 비교
  }
}

int main() {
  int i, N;
  vector<pair<int,int>> ps; // 좌표 쌍을 받을 벡터를 선언해 준다.

  cin >> N; // 좌표개수를 입력받는다.
  int x, y;
  for(i = 0; i < N; i++) { // 주어진 개수만큼 반복
    cin >> x >> y; // 좌표 x,y 값을 받아서
    ps.push_back({x, y}); // 좌표값을 추가해 준다.
  }
  
  sort(ps.begin(), ps.end(), compare); // 소팅
  for(i = 0; i < N; i++) { 
    cout << ps[i].first << ' ' << ps[i].second << '\n';
    // 소팅된 벡터를 하나씩 좌표형태로 출력해 준다.
  }
  return 0;
}