백준 13334번
오늘 풀어본 문제는 백준의 13334번 문제1이다. 문제 풀이에 사용한 언어는 C++ 이다.
solved.ac 기준 CLASS
문제 정보
이 문제의 내용과 조건은 다음과 같다.
문제
집과 사무실을 통근하는 $n$ 명의 사람들이 있다. 각 사람의 집과 사무실은 수평선 상에 있는 서로 다른 점에 위치하고 있다. 임의의 두 사람 $A$, $B$ 에 대하여, $A$ 의 집 혹은 사무실의 위치가 $B$ 의 집 혹은 사무실의 위치와 같을 수 있다. 통근을 하는 사람들의 편의를 위하여 일직선 상의 어떤 두 점을 잇는 철로를 건설하여, 기차를 운행하려고 한다. 제한된 예산 때문에, 철로의 길이는 $d$ 로 정해져 있다. 집과 사무실의 위치 모두 철로 선분에 포함되는 사람들의 수가 최대가 되도록, 철로 선분을 정하고자 한다.
양의 정수 $d$ 와 $n$ 개의 정수쌍, $(h_i,\ o_i)$, $1 \le i \le n$,이 주어져 있다. 여기서 $h_i$ 와 $o_i$ 는 사람 $i$ 의 집과 사무실의 위치이다. 길이 $d$ 의 모든 선분 $L$ 에 대하여, 집과 사무실의 위치가 모두 $L$ 에 포함되는 사람들의 최대 수를 구하는 프로그램을 작성하시오.
그림 1 에 있는 예를 고려해보자. 여기서 $n = 8$, $(h_1,\ o_1) = (5,\ 40)$, $(h_2,\ o_2) = (35,\ 25)$, $(h_3,\ o_3) = (10,\ 20)$, $(h_4,\ o_4) = (10,\ 25)$, $(h_5,\ o_5) = (30,\ 50)$, $(h_6,\ o_6) = (50,\ 60)$, $(h_7,\ o_7) = (30,\ 25)$, $(h_8,\ o_8) = (80,\ 100)$ 이고, $d = 30$ 이다. 이 예에서, 위치 $10$ 과 $40$ 사이의 빨간색 선분 $L$ 이, 가장 많은 사람들에 대하여 집과 사무실 위치 모두 포함되는 선분 중 하나이다. 따라서 답은 $4$ 이다.
입력
입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 $n$ $(1 \le n \le 100,000)$ 이 주어진다. 다음 $n$ 개의 각 줄에 정수 쌍 $(h_i,\ o_i)$ 가 주어진다. 여기서 $h_i$ 와 $o_i$ 는 $−100,000,000$ 이상, $100,000,000$ 이하의 서로 다른 정수이다. 마지막 줄에, 철로의 길이를 나타내는 정수 $d$ $(1 \le d \le 200,000,000)$ 가 주어진다.
출력
출력은 표준출력을 사용한다. 길이 $d$ 의 임의의 선분에 대하여, 집과 사무실 위치가 모두 그 선분에 포함되는 사람들의 최대 수를 한 줄에 출력한다.
풀이과정
1번째 시도
문제를 해결하기 위해 사용한 방식은 다음과 같다.
-
각 구간들을 입력받고, 왼쪽 위치를 기준으로 정렬되도록 우선순위 큐에 넣는다.
-
우선순위 큐에서 구간을 하나씩 꺼낸 뒤, 맨 앞에 있는 구간의 왼쪽 위치를 철로의 왼쪽 위치로 두었을 때 꺼낸 구간이 포함되면 계속해서 큐에 넣고, 포함되지 않을 때 현재 큐의 크기를 이용하여 최댓값을 갱신하고 큐의 맨 앞 원소를 제거한다.
-
우선순위 큐에서 모든 구간이 꺼내질 때까지 2를 반복한다.
코드는 다음과 같이 작성하였다.
#include <bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;
using ll = long long int;
using ull = unsigned long long int;
using pll = pair<ll, ll>;
using ld = long double;
struct cmp {
bool operator()(const pll& a, const pll& b) {
if (a.first == b.first) {
return a.second > b.second;
}
return a.first > b.first;
}
};
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll n;
cin >> n;
std::priority_queue<pll, vector<pll>, cmp> pq;
for (ll i=0; i<n; i++) {
ll h, o;
cin >> h >> o;
if (h > o) {
swap(h, o);
}
pq.push(make_pair(h, o));
}
ll d;
cin >> d;
ll maximum = 0;
queue<pll> q;
while (!pq.empty()) {
auto curr = pq.top();
pq.pop();
if (q.empty()) {
if (curr.second > curr.first + d) {
continue;
}
else {
q.push(curr);
maximum = max<ll>(maximum, q.size());
}
}
else {
while (!q.empty() && curr.second > q.front().first + d) {
q.pop();
}
if (q.empty() && curr.second > curr.first + d) {
continue;
}
else {
q.push(curr);
maximum = max<ll>(maximum, q.size());
}
}
}
cout << maximum;
return 0;
}
실행 결과 ‘틀렸습니다’ 가 떴다.
2번째 시도
처음 접근의 잘못되었던 부분은, 구간의 ‘왼쪽’ 위치가 아닌, ‘오른쪽’ 위치로 정렬을 실시해야 한다는 점이었다. 오른쪽 위치를 기준으로 정렬한 뒤, 왼쪽 위치들을 일반 큐가 아닌 우선순위 큐로 저장하게 하여 해결을 시도하였다.
코드는 다음과 같이 수정하였다.
#include <bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;
using ll = long long int;
using ull = unsigned long long int;
using pll = pair<ll, ll>;
using ld = long double;
struct cmp {
bool operator()(const pll& a, const pll& b) {
if (a.second == b.second) {
return a.first < b.first;
}
return a.second < b.second;
}
};
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll n;
cin >> n;
vector<pll> lines;
for (ll i=0; i<n; i++) {
ll h, o;
cin >> h >> o;
if (h > o) {
swap(h, o);
}
lines.emplace_back(make_pair(h, o));
}
sort(lines.begin(), lines.end(), cmp());
ll d;
cin >> d;
ll maximum = 0;
std::priority_queue<int, vector<int>, greater<int>> pq;
for (ll i=0; i<n; i++) {
auto curr = lines[i];
if (curr.second - curr.first <= d) {
pq.push(curr.first);
while (!pq.empty() && curr.second > pq.top() + d) {
pq.pop();
}
maximum = max<ll>(maximum, pq.size());
}
}
cout << maximum;
return 0;
}
그러자 모든 테스트 케이스를 통과하고 ‘맞았습니다’가 나오는 것을 확인할 수 있었다.
마무리
이 문제를 풀면서 스위핑 알고리즘이라는 것을 알게 되었다. 데이터들을 한 번씩 스캔해나가며 푸는 알고리즘들을 스위핑 알고리즘이라고 부르는데, 앞으로 가끔 보게 될 것 같은 기분이 든다.
오늘의 PS는 여기까지!
1: https://www.acmicpc.net/problem/13334