백준 알고리즘 11651번 좌표 정렬하기2(C++)

실버ⅴ

 

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

11651번: 좌표 정렬하기 2

 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	64946	42201	35958	66.792%

문제

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

입력

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

출력

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

예제 입력 1

5
0 4
1 2
1 -1
2 2
3 3

예제 출력 1

1 -1
1 2
2 2
3 3
0 4

 

풀이 방법

이전의 '좌표 정렬하기' 문제처럼 STL의 sort함수를 사용하면 알아서 vector의 first를 기준으로 정렬하고, first가 같으면 second를 기준으로 정렬하기 때문에 이를 활용하면 된다. 여기에 추가로 compare함수를 만들어 second를 기준으로 정렬하고, second가 같으면 first를 기준으로 정렬하도록 바꾸어주면 된다.

내 코드

#include <iostream>
using namespace std;
 
#include <algorithm>
#include <vector>
 
bool compare(pair<int,int> a, pair<int,int> b);
 
int main() {
    
    int n;
    cin >> n;
 
    vector<pair<int,int>> v;
    int x, y;
    for (int i = 0; i < n; i++) {
        cin >> x >> y;
        v.push_back({x, y});
    }
 
    sort(v.begin(), v.end(), compare);
 
    for (int i = 0; i < n; i++)
        cout << v[i].first << " " << v[i].second << "\n";
 
 
    return 0;
}
 
bool compare(pair<int,int> a, pair<int,int> b) {
    if (a.second < b.second)
        return true;
    else if (a.second == b.second) {
        if (a.first < b.first)
            return true;
        else
            return false;
    }
    else
        return false;
}

반응형

코드 설명

vector<pair<int,int>> v;

pair을 이용하면 값을 쌍으로 저장할 수 있다.

 

bool compare(pair<int,int> a, pair<int,int> b) {
	if (a.second < b.second)
		return true;
	else if (a.second == b.second) {
		if (a.first < b.first)
			return true;
		else
			return false;
	}
	else
		return false;
}

second를 기준으로 정렬하고, second가 같으면 first를 기준으로 정렬하도록 바꾸어주는 compare 함수이다.