본문 바로가기
알고리즘

[백준 11650] 알고리즘 14일차 : 좌표 정렬하기

by SiO2whocode 2020. 3. 15.
반응형

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

 

11650번: 좌표 정렬하기

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

www.acmicpc.net

[정렬] C++

처음엔 선택정렬로 x좌표 기준 정렬하고 y좌표 기준 따로 정렬했는데 시간초과 나서

pair 사용하는 코드로 제출했더니 맞음.

 

덕분에 pair 사용.. 헤더는 <utility>

pair<type, type> pair_name; //한쌍만 쓸때 사용

pair<type, type> pair_name[size]; //배열로도 가능

 

관련 함수

make_pair(변수, 변수); //두 변수를 하나의 pair로 만들어줌

//사용예시

pair_name[0] = make_pair(a, b);

pair_name.first  //첫번째 값 접근

pair_name.second  //두번째 값 접근

sort() 사용해서 정렬도 가능(첫번째 원소를 기준으로 정렬하고, 첫번째 원소가 같은 경우 두번째 원소를 정렬)

-> 이거 때문에 이 문제에서 pair쓰는게 아주 편했음

 

소스코드(pair사용)

 

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

int main(){
    int n;
    cin >> n;

 	pair<int, int> xy[n];
    
    int x, y;
    for(int i = 0 ; i < n ; i++){
        cin >> x >> y;
        xy[i] = make_pair(x, y);
    }
    
    sort(xy, xy+n);

    for(int i = 0 ; i < n ; i++)
        cout << xy[i].first << " " << xy[i].second << "\n";

    return 0;
}

 

 

 

소스코드(pair 미사용, 선택정렬)

 

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

int main(){
    int n;
    cin >> n;
    
    int x[n];
    int y[n];
    for(int i = 0 ; i < n ; i++)
        cin >> x[i] >> y[i];
    
    //X좌표 기준으로 정렬
    int minX, minIndex;
    for(int i = 0 ; i < n-1 ; i++){
        minX = x[i];
        minIndex = i;
        for(int j = i+1 ; j < n ; j++){
            if(minX > x[j]){
                minX = x[j];
                minIndex = j;
            }
        }
        if(minIndex != i){
            swap(x[i], x[minIndex]);
            swap(y[i], y[minIndex]);
        }
    }
    //Y좌표 기준 정렬
    int start = 0;
    for(int i = 0 ; i < n ; i++){
        if(x[i] != x[i+1]){
            sort(y+start, y+i+1);
            start = i+1;
        }
    }
    for(int i = 0 ; i < n ; i++){
        cout << x[i] << " " << y[i] << "\n";
    }
    return 0;
}
반응형

댓글0