[C++] 백준 13334. 철로

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

13334번: 철로

1. 문제

 

2. 아이디어

이 문제는 기본적으로 스위핑 알고리즘을 사용해서 풀이합니다.

스위핑 알고리즘은 뜻 그대로 휩쓸고 지나가며 문제를 해결하는 방식으로,

특정 기준에 따라 정렬한 후 순서대로 처리하는 알고리즘입니다.

 

그러므로 스위핑 알고리즘의 복잡도는 

O(N log N + N) = O(N log N) 의 복잡도를 가집니다.

 

즉, 이 문제는 선분을 특정 기준으로 정렬해서

쭉 순회하면서 해결하는 것이 주된 아이디어라는 것이죠.

3. 풀이

 

먼저 필요한 변수들을 저장해주고

배열에는 집과 사무실의 짝을 저장합니다.

 

 

적절하게 입력을 받아주고

(참고로 나중에 로직을 편하게 짜기 위해서, 최소값을 first에 최대값을 second에 넣었습니다.)

 

 

끝점을 기준으로 오름차순 정렬해줍니다.

 

자 그러면 정렬한 다음에 arr 배열 전체를 훑으면서 적절한 로직을 구현하는 것이 중요한데요.

 

 

문제에서 보면 알 수 있듯이

처음에 받아줬던 길이 d의 선분을 그을때

최대한 (집, 사무실) 좌표 쌍이 길이 d에 많이 포함되어 있어야합니다.

 

 

이런 식으로 쭉 훑으면서 예외처리를 해주고,

어떤 로직으로 직선을 구하냐가 중요한데

 

여기서 우선순위 큐를 사용할 것 입니다.

 

우선순위 큐를 사용한 알고리즘 로직은 다음과 같습니다.

1) 우선순위 큐는 (시작점) 좌표를 최소힙으로 정의한다.

2) 집~사무실의 거리가 d보다 긴 좌표쌍은 제외하고 전부 pq에 넣는다.

3) pq에는 시작점이 작은 좌표쌍이 떠오른다.

4) pq의 top에 있는 시작점이 방금 넣은 좌표쌍은 끝점 - d 보다 작으면 같은 직선에 포함되지 않는다는 것을 의미한다.

그러므로 pop() 을 하여 우선순위 큐에서 제거한다. ( while문을 돌려서 조건에 안맞는 좌표쌍 모두 제거)

 

여기서 pq 안에 있는 요소들은 모두 방금 넣은 좌표쌍과 같은 직선에 존재할 수 있는 좌표쌍입니다.

 

즉, O(N)으로 배열을 한 번 쭉 훑으면서 pq의 size가 최대일 때를 기록해두면 되는 것이죠.

 

 

이런 식으로 코드를 작성할 수 있습니다.

 

 

출력 코드고 아래는 전체코드 입니다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int N;
int d;
pair<int, int> arr[100'001];
priority_queue<int, vector<int>, greater<int>> pq;

struct Comp
{
    bool operator()(const pair<int, int>& a, const pair<int, int>& b) {
        if (a.second != b.second) {
            return a.second < b.second;
        }
        else if (a.second == b.second) {
            return a.first < b.first;
        }
    }
};

int main()
{

    /* 입력 */
    {
        cin >> N;

        for (int i = 0; i < N; i++)
        {
            int from, to;
            cin >> from >> to;

            arr[i] = make_pair(min(from, to), max(from, to));
        }

        cin >> d;

    }

    int rst = 0;

    /* 로직 */
    {
        /* 정렬 */
        std::sort(arr, arr + N, Comp());

        for (int i = 0; i < N; i++)
        {
            int distance = arr[i].second - arr[i].first; /* 길이를 구한다. */

            if (distance > d)
                continue; /* 만약 집~사무실의 거리가 d보다 길면 아예 직선을 못긋겠죠?*/

            pq.push(arr[i].first); /* 후보에 넣어둠 */

            while (!pq.empty())
            {
                if (arr[i].second - d > pq.top())
                    pq.pop();
                else break;
            }

            rst = max(rst, static_cast<int>(pq.size()));
        }
    }

    /* 출력 */
    {
        cout << rst << endl;
    }

    return 0;
}

 

 

개인적으로 살짝 어려운 문제였습니다.