[백준 BOJ 11651번] 좌표 정렬하기 2(C / C++ ) [정렬, 우선순위큐]

11651번: 좌표 정렬하기 2 (acmicpc.net)

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1초	256MB	22979	15359	12974	68.959%

 

문제

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

 

입력

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

 

출력

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

 

예제 입력 1

5
0 4
1 2
1 -1
2 2
3 3

 

예제 출력 1

1 -1
1 2
2 2
3 3
0 4

 

풀이

C++ STL와 내장함수를 적극 이용하여 문제를 풀었습니다.

제가 아는 선에서 설명드리는 것이므로 틀린 부분이 있으면 지적해주시면 감사드리겠습니다.

우선 pair구조를 내장된 정렬함수를 이용해 정렬하면 first의 우선순위가 second보다 앞서는 것으로 알고 있습니다.

문제에서는 y값을 우선 오름차순으로 정렬, x,y값이 같으면 y값이 같으면 x값을 오름차순으로 정렬하는 것으로 되어있습니다.

sort함수를 이용 시, 비교 함수를 선언해도 되지만 아까 말씀드렸다시피 pair구조는 first가 우선순위를 지닌다는 점을 이용하여 데이터를 입력 시에 

    first <- y

    second <- x

순으로 넣어주시면 y값을 기준으로 오름차순 정렬을 하게 됩니다.

 출력 시에는 x y좌표 순으로 출력을 해야 하니 second를 먼저 출력합니다.

 

두 번째로는 우선순위 큐 자료구조를 이용한 풀이입니다. 이 또한 pair 구조의 성질을 이용하여 풀었습니다.

우선순위 큐는 기본적으로 Max Heap을 이용하기 때문에 top에 들어오는 값은 최대값이 되어 내림차순 정렬이 됩니다.

이를 오름차순으로 바꿔주는 것에는 여러가지 방법이 있지만 가장 쉬운 방법이자 트릭은 큐에 push할 때 값에 -(마이너스)를 하여 반전된 값을 push해주고 꺼낼 때는 또 다시 -(마이너스)를 하여 원상복구 시켜주는 것입니다.

만약 우선순위 큐에 들어갈 값이 3, 5, 4, 1 2 일 때 큐가 빌 때 까지 값을 꺼내 보면

5, 4, 3, 2, 1이 나오지만 방금 제가 말씀드린대로 하게 되면,

우선순위 큐 내에서는 -1, -2, -3, -4, -5순으로 값이 저장이 될 것이고 꺼낼 때 다시 마이너스를 하면

1, 2, 3, 4, 5가 출력이 됩니다. 이 성질을 이용해 첫 번째 방법과 동일하게 문제를 해결하면 됩니다

데이터 타입의 구조 상 우선순위 큐를 이용한 풀이가 메모리 소모와 무의미하지만 약간의 시간 차도 보입니다.

 

코드

// 좌표 정렬하기 2
#include<bits/stdc++.h>
using namespace std;
int main(){
    ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
    int n,x,y;
    cin>>n;
    vector<pair<int,int>> a(n);
    for(int i=0;i<n;i++){
        cin>>x>>y;
        a[i]={y,x};
    }
    sort(a.begin(),a.end());
    for(int i=0;i<n;i++)cout<<a[i].second<<" "<<a[i].first<<"\n";
}

 

// 좌표 정렬하기 2 우선순위큐
#include<bits/stdc++.h>
using namespace std;
priority_queue<pair<int,int>> a;
int main(){
    ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
    int n,x,y;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>x>>y;
        a.push({-y,-x}); //<-- -를 넣어 값을 뒤집어줘 우선순위를 뒤집어줌
    }
    while(!a.empty()){ //출력 시 뒤집힌 값을 다시 원상복구한 후 출력
        cout<<-a.top().second<<" "<<-a.top().first<<"\n";
        a.pop();
    }
}

11651번: 좌표 정렬하기 2 (acmicpc.net)

11651번: 좌표 정렬하기 2