[11650번] 좌표 정렬하기

문제 출처 :

 

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. x,y 좌표를 정렬 하는 방법

2. 구조체를 이용한 x,y 좌표 묶기

x에 대해 정렬하고 그리고 y에 대해 정렬을 하려고 하면, x값이 같이 따라오지 않는 현상이 발생 할 수 있다.

이를 위해 구조체로 x,y를 묶어두면 조금 더 간단하게 해결할 수 있게된다.

두가지 소스 코드를 볼 때, 

첫번째 코드는 퀵 소트를 구조체에 적용시킨 것,

두번째 코드는 이러한 방식이 그대로 녹아있는 정렬 알고리즘(c++에 내포)을 확인한다.

소스 코드 : 

- 1번 코드 -

#include <stdio.h>
 
 
typedef struct xy
{
    int x;
    int y;
}Map;
 
Map map[100001];
 
void SwapX(int a, int b) // a,b 스왑 함수 
{
    Map temp = map[a];
    map[a] = map[b];
    map[b] = temp;
}
 
int PartitionX(int left, int right)
{
    Map pivot = map[left]; // 피벗의 위치는 가장 왼쪽에서 시작
    int low = left + 1;
    int high = right;
 
 
    while (low <= high) // 교차되기 전까지 반복한다 
    {
        while (pivot.x >= map[low].x && low <= right) // 피벗보다 큰 값을 찾는 과정 
        {
            low++; // low를 오른쪽으로 이동 
        }
 
        while (pivot.x <= map[high].x && high >= (left + 1)) // 피벗보다 작은 값을 찾는 과정 
        {
            high--; // high를 왼쪽으로 이동
        }
 
        if (low <= high)// 교차되지 않은 상태이면 스왑 과정 실행 
        {
            SwapX(low, high); //low와 high를 스왑 
        }
 
    }
    SwapX(left, high); // 피벗과 high가 가리키는 대상을 교환 
    return high;  // 옮겨진 피벗의 위치정보를 반환 
 
}
 
 
void QuickSortX(int left, int right)
{
    if (left <= right)
    {
        int pivot = PartitionX(left, right); // 둘로 나누어서
        QuickSortX(left, pivot - 1); // 왼쪽 영역을 정렬한다.
        QuickSortX(pivot + 1, right); // 오른쪽 영역을 정렬한다.
    }
}
 
 
 
 
 
void SwapY(int a, int b) // a,b 스왑 함수 
{
    Map temp = map[a];
    map[a] = map[b];
    map[b] = temp;
}
 
int PartitionY(int left, int right)
{
    Map pivot = map[left]; // 피벗의 위치는 가장 왼쪽에서 시작
    int low = left + 1;
    int high = right;
 
 
    while (low <= high) // 교차되기 전까지 반복한다 
    {
        while (pivot.y >= map[low].y && low <= right) // 피벗보다 큰 값을 찾는 과정 
        {
            low++; // low를 오른쪽으로 이동 
        }
 
        while (pivot.y <= map[high].y && high >= (left + 1)) // 피벗보다 작은 값을 찾는 과정 
        {
            high--; // high를 왼쪽으로 이동
        }
 
        if (low <= high)// 교차되지 않은 상태이면 스왑 과정 실행 
        {
            SwapY(low, high); //low와 high를 스왑 
        }
 
    }
    SwapY(left, high); // 피벗과 high가 가리키는 대상을 교환 
    return high;  // 옮겨진 피벗의 위치정보를 반환 
 
}
 
 
void QuickSortY(int left, int right)
{
    if (left <= right)
    {
        int pivot = PartitionY(left, right); // 둘로 나누어서
        QuickSortY(left, pivot - 1); // 왼쪽 영역을 정렬한다.
        QuickSortY(pivot + 1, right); // 오른쪽 영역을 정렬한다.
    }
}
 
 
 
 
 
int main()
{
 
    int n, i;
    int start, end;
    int cnt = 0;
    scanf("%d", &n);
 
    for (i = 0; i < n; i++)
        scanf("%d %d", &map[i].x, &map[i].y);
 
 
    QuickSortX(0, n - 1);
 
    i = 1;
    start = 0;
    end = n - 1;
    while (i < n)
    {
        if (map[i].x == map[i - 1].x)
        {
            cnt = 1;
            start = i - 1;
            while (map[i].x == map[i - 1].x)
            {
                end = i;
                i++;
            }
        }
 
        if (cnt >= 1)
        {
            QuickSortY(start, end);
            start = i;
 
        }
        cnt = 0;
        i++;
    }
    for (i = 0; i < n; i++)
        printf("%d %d\n", map[i].x, map[i].y);
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

- 2번 코드 -

이 코드는 구조체 x,y를 가진 후 sort라는 알고리즘을 이용하는 방법이다.

sort(시작, 끝+1, 조건);의 방식을 가지고 있는 코드이다.

자세한 내용은 이 게시물 다음 sort알고리즘 설명에서 참조할 수 있다. 

#include <cstdio>
#include <algorithm>
 
struct point {
    int x, y;
};
 
point p[100000];
 
bool comp(point const& a, point const& b){
    if(a.x == b.x) return a.y < b.y;
    return a.x < b.x;
}
 
int main() {
    int i, n, x, y;
    scanf("%d", &n);
    for(i=0; i<n; ++i){
        scanf("%d %d ", &x, &y);
        p[i] = {x, y};
    }
    std::sort(p, p+n, comp);
    for(i=0; i<n; ++i){
        printf("%d %d\n", p[i].x, p[i].y);
    }
    return 0;
}