컴공댕이 공부일지
[ C++/cpp ] 백준 (11561 좌표 정렬하기2) ⭐pair vector 정렬, 비교함수 본문
728x90
백준 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);
728x90
'문제 풀이 > 코딩 문제 풀이 모음' 카테고리의 다른 글
[ C++/cpp ] 백준 (5430 AC) ⭐구현, 덱 (5) | 2024.10.08 |
---|---|
[ C++/cpp ] 백준 (1654 랜선 자르기) ⭐이분 탐색 💦 (0) | 2024.07.20 |
[ C++/cpp ] 백준 (2108 통계학) ⭐최빈값 구하기, 최장 길이 부분 수열 (0) | 2024.07.11 |
[ C++/cpp ] 백준 (1018 체스판 다시 칠하기) ⭐브루트포스 알고리즘 (1) | 2024.03.29 |
[ C++/cpp ] 백준 (2839 설탕 배달) ⭐그리디 알고리즘 (1) | 2024.03.28 |
Comments