백준 13334 c++ "철로" -PlusUltraCode-

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

[필자 사고]

WellKnown 문제라고 할까?

대표적으로 시작점 혹은 끝점을 정렬한뒤 큐에 넣고 큐의 size를 이용하여 갯수를 갱신하는 문제다.

조심해야 될 부분은 queue의 값을 빼는 타이밍이다.

 

이번 문제는 end값을 기준으로 정렬한 뒤 start를 pq에 넣어논다. pq의 정렬 기준은 오름차순이다.

만약 end-D 가 pq.top()보다 크다면 갱신해야 될 타이밍이다.

pq.top()를 빼주는 형태로

 

아래는 자세한 코드 해설이다.

[코드 해설]

문제 요약

집과 사무실이 각각 수평선상의 한 점으로 주어진다.
각 사람은 [집, 사무실]이라는 구간을 가진다고 볼 수 있다.
이제 길이 D의 철로를 선분 형태로 설치했을 때,
집과 사무실이 모두 철로 안에 포함되는 사람의 최대 수를 구해야 한다.

즉, 철로의 길이 D를 고정했을 때

철로 구간 [x, x+D] 안에 완전히 포함되는 구간 [start, end]의 개수를 최대로 만드는 문제다.

---

접근 아이디어

이 문제는 단순한 완전 탐색으로는 해결할 수 없다.
(최대 100,000명 × 여러 위치를 고려해야 하므로 시간 초과 발생)

따라서 효율적으로 처리하기 위해
정렬 + 우선순위 큐(최소 힙) 를 이용한 스위핑(Line Sweeping) 방식을 사용한다.

---

핵심 원리

1. 각 사람의 구간을 [min(집, 사무실), max(집, 사무실)] 형태로 저장한다.
   (어느 쪽이 더 큰지는 중요하지 않기 때문)
2. end 기준으로 오름차순 정렬한다.
   → 즉, 철로의 오른쪽 끝을 end에 맞춘다고 생각한다.
3. 현재 고려 중인 철로의 왼쪽 끝은 end - D가 된다.
4. 모든 구간 중에서
   start >= end - D를 만족하는 구간은 현재 철로 안에 들어올 수 있다.
   이를 우선순위 큐로 관리하면서 현재 철로 범위에 포함된 사람의 수를 계산한다.
5. 매번 포함된 사람 수의 최댓값을 갱신한다.

---

알고리즘 흐름

1. 모든 구간 [start, end] 저장
2. end 기준으로 정렬
3. 하나씩 보면서
   • 현재 구간 길이가 D보다 긴 경우는 제외 (end - start > D)
   • 해당 구간의 start를 PQ에 넣기
   • PQ 안에서 start < end - D인 구간 제거
     (즉, 현재 철로 범위 [end-D, end]에 들어오지 못하는 사람 제외)
4. PQ의 크기 = 현재 철로로 커버 가능한 사람 수
5. 그 중 최댓값을 저장 후 출력

[소스 코드]

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
struct Node {
	int start;
	int end;
};
int N,D;
vector<Node> arr;

bool cmp(Node a, Node b) {
	return a.end < b.end;
}


int main(void) {
	cin >> N;

	for (int i = 0; i < N; i++) {
		int start, end;
		cin >> start >> end;
		int minNum = min(start, end);
		int maxNum = max(start, end);

		arr.push_back({ minNum,maxNum });
	}

	sort(arr.begin(), arr.end(),cmp);
	priority_queue<int, vector<int>, greater<int>> pq;

	int minStartTime = arr[0].start;
	int answer = -1;
	
	for (int i = 0; i < arr.size(); i ++ ) {
		int start = arr[i].start;
		int end = arr[i].end;

		if (end - start > D)continue;

		pq.push(start);

		while (!pq.empty() && pq.top() < end - D) {
			pq.pop();
		}

		answer = max(answer, (int)pq.size());
	}

	cout << answer;
}