[BaekJoon 11651][⚪5] 좌표 정렬하기 2

❓ 문제

백준 11651 - “좌표 정렬하기 2”

🎯 난이도

Silver ⚪5

🧠 풀이

1. 내 풀이 (구조체 + 정렬)

- 알고리즘

• Sorting

- 설명

구조체를 이용해 정렬하는 방식의 풀이이다.

좌표에 대응하는 구조체를 만들고, 내부에 비교 연산자 오버로딩을 통해 자동 정렬되도록 하는 방식이다.

전체 시간 복잡도는 곧 sort의 시간 복잡도이므로 O(N log N)이다.

- 코드

내 풀이 코드

#include <iostream>

#include <vector>

#include <algorithm>

#include <sstream>


using namespace std;

struct Coord
{
    int iX{}, iY{};

    // 비교 연산자 operator 오버로딩
    bool operator<(const Coord& tOther) const
    {
        if(iY == tOther.iY)
        {
            return iX < tOther.iX;
        }

        return iY < tOther.iY;
    }
};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int iN{};
    cin >> iN;

    vector<Coord> vecCoord;
    vecCoord.reserve(iN);

    while(iN--)
    {
        int iX{}, iY{};
        cin >> iX >> iY;

        vecCoord.emplace_back(Coord{iX, iY});
    }

    sort(vecCoord.begin(), vecCoord.end());

    // ostringstream으로 한 번에 출력
    ostringstream ssOut{};
    for(const auto& tCoord : vecCoord)
    {
        ssOut << tCoord.iX << ' ' << tCoord.iY << '\n';
    }

    cout << ssOut.str();

    return 0;
}

---

2. 추가 풀이 (pair + 정렬)

- 알고리즘

• Sorting

- 설명

pair를 이용한 정렬을 사용하는 방식이다.

pair의 "First 비교 -> Second 비교" 특성을 사용하는 방식이다.

주의할 점은, Y 먼저 비교하고 X를 비교하므로 입력에서 반대로 입력 받고, 출력에서 다시 반대로 출력해야 한다는 점이다.

위의 풀이와 마찬가지로 시간 복잡도는 O(N log N)이다.

- 코드

내 풀이 코드

#include <iostream>

#include <vector>

#include <algorithm>

#include <sstream>


using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int iN{};
    cin >> iN;

    vector<pair<int, int>> vecCoord;
    vecCoord.reserve(iN);

    while(iN--)
    {
        int iX{}, iY{};
        cin >> iX >> iY;

        // iX, iY 순서 바꿔서 저장
        vecCoord.emplace_back(pair{iY, iX});
    }

    // iY -> iX 순으로 비교
    sort(vecCoord.begin(), vecCoord.end());

    ostringstream ssOut{};
    for(const auto& pairCoord : vecCoord)
    {
        // 출력은 iX -> iY 순으로
        ssOut << pairCoord.second << ' ' << pairCoord.first << '\n';
    }

    cout << ssOut.str();

    return 0;
}

---

💭 후기

이 문제는 좌표 정렬하기의 변형 버전이다.

다른 점은 전에는 X -> Y 순으로 비교였지만, 여기서는 Y -> X 순으로 비교해야 한다는 것이다. 이것만 잘 생각해서 풀면 된다!