[BaekJoon 11650][⚪5] 좌표 정렬하기

❓ 문제

백준 11650 - “좌표 정렬하기”

🎯 난이도

Silver ⚪5

🧠 풀이

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

- 알고리즘

• Sorting

- 설명

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

좌표에 대응하는 구조체를 정의하고, 내부에 비교 연산자 operator을 오버로딩해서 sort로 정렬할 떄 자동으로 정렬되도록 만들었다.

구조체 내부에 연산자 오버로딩을 하는 방식은 람다식을 쓰는 것과 다르지 않지만 새로운 방식으로 해보고 싶었다.

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(iX == tOther.iX)
        {
            return iY < tOther.iY;
        }

        return iX < tOther.iX;
    }
};

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

    int iN{};
    cin >> iN;

    vector<Coord> vecCoord(iN);

    for(int i = 0; i < iN; ++i)
    {
        cin >> vecCoord[i].iX >> vecCoord[i].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'를 비교한다. 따라서 그냥 sort만 쓰더라도 알아서 순서대로 정렬이 된다.

위의 풀이와 마찬가지로 시간 복잡도는 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(iN);

    for(int i = 0; i < iN; ++i)
    {
        cin >> vecCoord[i].first >> vecCoord[i].second;
    }

    // pair는 first -> second 순으로 비교하므로 비교 함수 객체 필요 없음
    sort(vecCoord.begin(), vecCoord.end());

    // ostringstream으로 한 번에 출력하기
    ostringstream ssOut{};
    for(const auto& pairCoord : vecCoord)
    {
        ssOut << pairCoord.first << ' ' << pairCoord.second << '\n';
    }

    cout << ssOut.str();

    return 0;
}

---

💭 후기

좀 더 가독성을 챙기기 위해 구조체를 사용하고 연산자 오버로딩도 해봤는데, 사실 pair로만 해도 충분한 문제이다.

추가적으로 이번에 출력을 ostringstream을 사용해서 해봤는데, 이는 전에 수 정렬하기 2에서 string을 써서 했던 방식과는 조금 다른 방식이다.

ostringstream은 비교적 단순하고 편하지만, '내부 버퍼'가 조금 더 생기므로 속도에 민감하면 string을 사용하는 방식으로 하는 게 좋다.