백준 #11651 / 좌표 정렬하기 2

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	2735	1692	1422	65.955%

문제

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

입력

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

출력

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

---

단순한 문제지만, STL의 sort 특징을 알게되어서 포스팅해본다.

우선, 나는 MergeSort로 하나 하나 코딩했다.

[How To Solve?]

- N * 2 크기의 2차원 배열 생성

- N행 0열에는 x좌표, 1열에는 y좌표를 저장한다.

- mergeSort를 이용하여, y좌표가 같은경우와 같지 않은 경우로 나눈다.

- 같은 경우, x좌표의 대소 비교를 또 조건에 넣어 다뤄준다.

[Code]

#include<iostream>
using namespace std;
 
void mergeSort(int, int, int**);
void merge(int, int, int, int**);
int **result;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int N;
    cin >> N;
 
    int **arr = new int*[N];
    result = new int*[N];
    for (int i = 0; i < N; i++) {
        arr[i] = new int[2];
        result[i] = new int[2];
    }
 
    for (int i = 0; i < N; i++) 
        cin >> arr[i][0] >> arr[i][1];
    
    mergeSort(0, N - 1, arr);
 
    for (int i = 0; i < N; i++) 
        printf("%d %d\n", result[i][0], result[i][1]);
 
    return 0;
}
 
void mergeSort(int left, int right, int **arr) {
    int mid;    // 가운데 인덱스
    if (left < right) {    // left가 right와 같아지는 순간 정렬 끝.
        mid = (left + right) / 2;
        mergeSort(left, mid, arr);
        mergeSort(mid+1, right, arr);
        merge(left, mid, right, arr);
    }
}
 
void merge(int left, int mid, int right, int **arr) {
    int l = left;    
    int m = mid + 1;
    int k = left;
 
    while (l <= mid || m <= right) {
 
        if (l<= mid && m <= right) {    // 비교해야할 배열이 쪼개진 배열 둘 다 남아있는 경우
            if (arr[l][1] == arr[m][1]) // y좌표가 같은 경우
            {
                if (arr[l][0] <= arr[m][0]) {    // m의 x좌표가 더 크거나 같은경우
                    result[k][0] = arr[l][0];
                    result[k][1] = arr[l++][1];
                }
                else    // l의 x좌표가 더 큰 경우
                {
                    result[k][0] = arr[m][0];
                    result[k][1] = arr[m++][1];
                }
            }
            else if (arr[l][1] > arr[m][1]) {    // l의 y좌표가 m의 y좌표보다 큰 경우
                result[k][0] = arr[m][0];
                result[k][1] = arr[m++][1];
            }
            else
            {
                result[k][0] = arr[l][0];
                result[k][1] = arr[l++][1];
            }
        }
        else if (l <= mid && m > right) {    // l에만 남아있음
            result[k][0] = arr[l][0];
            result[k][1] = arr[l++][1];
        }
        else {
            result[k][0] = arr[m][0];
            result[k][1] = arr[m++][1];
        }
        k++;
    }
    for (int i = left; i < right + 1; i++) {
        arr[i][0] = result[i][0];
        arr[i][1] = result[i][1];
    }
}

// 주석

- 실행시간이 68MS... 1등은 32MS

- 무슨 차이인가 싶어서 1등 코드를 봤으나 이해불가... 2등인 40MS로 넘어가서 확인해본 결과, STL의 sort를 사용했다.

// 뭘 알게 되었는가?

- pair로 짝을 만들어놓는다. 예를 들어, xy좌표평면이라면 pair<int,int>

- 궁금해서 3차원 공간좌표로 바꿔서 pair<int, pair<int, int> >로 바꿨다.

- sort를 사용하게 되면, pair의 경우 first부터 차례대로 정렬된다.

- 무슨 말이냐면, pair는 first와 second를 갖고 있지 않은가?

- 입력을 거꾸로 second first로 받으면 y좌표가 x로 들어가고 x좌표가 y로 들어가게 된다.

- 결국에는 y좌표를 정렬한 후 x좌표를 정렬한다는 것.

- 출력할 때에는 입력받은 순서대로 그대로 출력하면 된다.

[Code]

#include <iostream>
#include <algorithm>
using namespace std;
 
pair<int, pair<int, int> > Input[100005];
int N;
 
int main()
{
    //freopen("input.txt", "r", stdin);
 
    cin.sync_with_stdio(false);
    cin >> N;
    int x, y;
    for (int i = 0; i < N; i++)
        cin >> Input[i].second.first >> Input[i].first >> Input[i].second.second;
 
    sort(Input, Input + N);
 
    for (int i = 0; i < N; i++)
        printf("%d %d %d\n", Input[i].first, Input[i].second.first, Input[i].second.second);
}

// 추가

- 그렇다면, 2차원 배열로도 가능할까?

- 이건 나중에... 잘 모르겠다 만약 STL을 쓸 수 없는 경우에는 mergeSort를 이용하는 것이 편할듯 싶다.