N개의 좌표 점 P가 (xi, yi) 형태로 주어져 있다고 가정해 보겠습니다. 여기서 x와 y 값은 1부터 N까지 자연수의 순열(permutation)로 이루어져 있습니다. 1부터 N 사이의 각 k에 대해 우리는 k번 도시에 있으며, 원하는 만큼 여러 번 연산을 수행할 수 있습니다. 여기서 연산이란, 현재 위치한 도시보다 x좌표와 y좌표가 모두 작은 도시 또는 x좌표와 y좌표가 모두 큰 도시로 이동하는 것을 의미합니다. 이때 k번 도시에서 도달할 수 있는 도시의 총 개수를 구해야 합니다.
예를 들어 입력이 P = [[1, 4], [2, 3], [3, 1], [4, 2]]와 같다면 출력은 [1, 1, 2, 2]가 됩니다. 앞의 두 도시 ((1, 4), (2, 3))는 조건을 만족하는 다른 도시로 이동할 수 없어 자기 자신만 도달 가능하고, 뒤의 두 도시 ((3, 1), (4, 2))는 서로 왕래할 수 있으므로 각각 2를 반환합니다.
풀이 단계
이 문제는 다음 단계를 따라 해결할 수 있습니다 −
n := P의 크기
2차원 배열 lst 정의
i := 0부터 시작하여 i < n인 동안 (반복마다 i를 1씩 증가):
v := { P[i, 0], P[i, 1], i }
v를 lst의 끝에 삽입
배열 lst 정렬
y_min := 1e9
집합 se 정의
크기가 n이고 0으로 초기화된 배열 ans 정의
i := 0부터 시작하여 i < n인 동안 (반복마다 i를 1씩 증가):
y_min := y_min과 lst[i, 1] 중 최솟값
lst[i, 2]를 se에 삽입
만약 y_min + i가 n과 같다면:
se의 각 원소 j에 대해
ans[j] := se의 크기
집합 se 비우기
만약 i가 n - 1과 같다면:
se의 각 원소 j에 대해
ans[j] := se의 크기
i := 0부터 시작하여 i < n인 동안 (반복마다 i를 1씩 증가):
ans[i] 출력
알고리즘의 핵심 아이디어
x좌표 기준으로 정렬한 뒤 앞에서부터 점을 살펴볼 때, 지금까지 처리한 점이 i+1개이고 그중 최소 y값이 n−i라면, 해당 점들이 y값 기준 상위 i+1개를 정확히 차지하게 됩니다(y값이 순열이므로). 이 순간 경계 앞의 점과 뒤의 점은 x와 y의 대소 관계가 엇갈려 있어 서로 직접 이동할 수 없습니다. 반면 같은 그룹 내부에서는 y값이 가장 작은 점이 나머지 모든 점과 직접 연결되므로, 그룹 전체가 하나의 도달 가능 집합이 됩니다. 따라서 위 조건이 만족될 때마다 지금까지 모은 집합 se의 크기를 각 원소의 정답으로 기록하면 됩니다. 정렬이 포함되므로 전체 시간 복잡도는 O(n log n)입니다.
예제 코드
아래 구현을 통해 더 자세히 이해해 보겠습니다 −
#include <bits/stdc++.h>
using namespace std;
void solve(vector<vector<int>> P){
int n = P.size();
vector<vector<int>> lst;
for (int i = 0; i < n; i++){
vector<int> v = { P[i][0], P[i][1], i };
lst.push_back(v);
}
sort(lst.begin(), lst.end());
int y_min = 1e9;
set<int> se;
vector<int> ans(n, 0);
for (int i = 0; i < n; i++){
y_min = min(y_min, lst[i][1]);
se.insert(lst[i][2]);
if (y_min + i == n){
for (auto j : se)
ans[j] = se.size();
se.clear();
}
if (i == n - 1){
for (auto j : se)
ans[j] = se.size();
}
}
for (int i = 0; i < n; i++){
cout << ans[i] << ", ";
}
}
int main(){
vector<vector<int>> P = { { 1, 4 }, { 2, 3 }, { 3, 1 }, { 4, 2 } };
solve(P);
}
입력
{ { 1, 4 }, { 2, 3 }, { 3, 1 }, { 4, 2 } }
출력
1, 1, 2, 2,