[ C++/cpp ] 백준 (11561 좌표 정렬하기2) ⭐pair vector 정렬, 비교함수

백준 11561번 좌표 정렬하기 2

(실버 5)

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

이전에 풀었던 좌표 정렬하기는 x 오름차순 우선이었는데, 이번 좌표 정렬하기2 는 y부터 오름차순 정렬하는 것이 다른 점다.

 

 

(정답 코드)

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
typedef pair<int,int> p;

bool compare (const p &a, const p &b) {
    
    if(a.second != b.second) { // y 좌표가 다른 경우,
        return a.second < b.second; // 작은 값이 앞에 오면 참이 되도록 (y 오름차순)
    } 
    else { // y 좌표가 똑같은 경우
        return a.first < b.first; // 더 작은 x가 앞에 오도록 (x 오름차순) 
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int n;
    p temp;
    vector<p> xy; // 좌표 저장할 페어타입 벡터
    
    // 입력
    cin >> n;
    while(n--) {
        cin >> temp.first >> temp.second;
        xy.push_back(temp);
    }
    
    // 연산
    sort(xy.begin(), xy.end(), compare); // 비교함수 활용해 좌표 정렬
    
    // 출력
    for(int i=0; i<xy.size(); i++) {
        cout << xy[i].first << " " << xy[i].second << "\n";
    }

    
    return 0;
}

 

 

📖 풀이 요약

pair 타입으로 x, y 좌표를 입력받아 벡터에 한쌍씩 저장해두었다.

 

그리고 비교함수를 정의

y가 다른 경우엔 작은 y부터 정렬되도록 / y가 같은 경우엔 작은 x부터 정렬되도록 했다.

 

 

🔎 vector<pair<int, int>> 정렬하기

 사실 pair 타입을 sort 함수로 정렬하면 디폴트가 first부터 정렬하는 거라, y 좌표를 first에 x좌표를 second에 저장하고, sort(bigin, end) 해버리면 자연스레 의도한 바 대로 잘 정렬된다. 실제로 그렇게 풀이한 분들도 있었다

 

 그치만 비교함수 정렬 복습도 할 겸, 문제 요구사항을 명확히 반영한 비교함수를 하나 정의했다.

x와 y를 순차대로 first, second에 저장하고, 아래 비교함수를 조직했다.

bool compare (const p &a, const p &b) {
    
    if(a.second != b.second) { // y 좌표가 다른 경우,
        return a.second < b.second; // 작은 값이 앞에 오면 참이 되도록 (y 오름차순)
    } 
    else { // y 좌표가 똑같은 경우
        return a.first < b.first; // 더 작은 x가 앞에 오도록 (x 오름차순) 
    }
}

// 비교함수 활용해 좌표 정렬
sort(xy.begin(), xy.end(), compare);