백준 2881 : 산책길
등급 : Gold III
2881번: 산책길 (acmicpc.net)
2881번: 산책길
정부는 오크 나무 숲을 통과하는 산책길를 만들려고 한다. 숲을 평면으로 나타낼 수 있고, 나무 N개는 평면위의 격자점으로 나타낼 수 있다. 산책길은 축에 평행한 직사각형으로 나타낸다. 산책
www.acmicpc.net
사용 알고리즘 : Binary Search
사용 자료구조 : Vector, Set, Map
이분 탐색의 upper_bound와 lower_bound를 이용하여 푸는 문제.
위의 그림에서 표시한 (2, 2) ~ (4, 4)의 경우, 경계에 존재하는 나무 3그루를 제거해야 한다.
이를 수행하려면 아래와 같은 과정이 필요하다.
1) x가 2이면서 y가 2~4인 나무의 갯수 합
2) x가 4이면서 y가 2~4인 나무의 갯수 합
3) y가 2이면서 x가 2~4인 나무의 갯수 합
4) y가 4이면서 x가 2~4인 나무의 갯수 합
5) (2, 2)에 나무가 있는 경우 1개 감소 (1~4의 과정에서 꼭짓점은 두 번 더하게 되기 때문)
6) (2, 4)에 나무가 있는 경우 1개 감소
7) (4, 2)에 나무가 있는 경우 1개 감소
8) (4, 4)에 나무가 있는 경우 1개 감소
이때 일반적인 배열로 이분 탐색을 하게 되면 범위 바깥의 나무도 더해지게 된다.
때문에 x좌표, y좌표에 따른 배열을 따로 생성해준다.
이를 토대로 이분 탐색(upper_bound, lower_bound)을 이용해 범위 내에 몇 개의 나무가 있는지 검사한다.
이후 꼭짓점의 좌표가 존재하는지 확인 후 갯수를 출력한다.
C++의 경우 내장된 upper_bound와 lower_bound, 그리고 set과 map의 기능으로 쉽게 풀이할 수 있지만,
Java의 경우 직접 구현해줘야 하며, contains 함수가 object의 경우 주소값으로 비교를 하기 때문에 이를 수정해줘야 한다.
#include <iostream>
#include <vector>
#include <set>
#include <unordered_map>
#include <algorithm>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, p;
unordered_map <int, vector <int>> posx, posy;
set <pair <int, int>> s;
cin >> n;
for (int i = 0; i < n; i++)
{
int x, y;
cin >> x >> y;
posx[x].push_back(y);
posy[y].push_back(x);
s.insert({ x, y });
}
for (auto &v : posx) sort(v.second.begin(), v.second.end());
for (auto &v : posy) sort(v.second.begin(), v.second.end());
cin >> p;
for (int i = 0; i < p; i++)
{
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
int ans = 0;
ans += upper_bound(posx[x1].begin(), posx[x1].end(), y2) - lower_bound(posx[x1].begin(), posx[x1].end(), y1);
ans += upper_bound(posx[x2].begin(), posx[x2].end(), y2) - lower_bound(posx[x2].begin(), posx[x2].end(), y1);
ans += upper_bound(posy[y1].begin(), posy[y1].end(), x2) - lower_bound(posy[y1].begin(), posy[y1].end(), x1);
ans += upper_bound(posy[y2].begin(), posy[y2].end(), x2) - lower_bound(posy[y2].begin(), posy[y2].end(), x1);
if (s.find({ x1, y1 }) != s.end()) ans--;
if (s.find({ x1, y2 }) != s.end()) ans--;
if (s.find({ x2, y1 }) != s.end()) ans--;
if (s.find({ x2, y2 }) != s.end()) ans--;
cout << ans << "\n";
}
}
import java.io.*;
import java.util.*;
public class Main {
static class pair {
int first;
int second;
pair(int first, int second) {
this.first = first;
this.second = second;
}
@Override
public boolean equals(Object obj)
{
pair other = (pair)obj;
if(this.first == other.first && this.second == other.second) return true;
else return false;
}
@Override
public int hashCode()
{
return Objects.hash(first, second);
}
}
static int upper_bound(int x, List<Integer> v)
{
if(v == null) return 0;
int left = 0;
int right = v.size();
while(left < right)
{
int mid = (left + right) / 2;
if(x >= v.get(mid)) left = mid + 1;
else right = mid;
}
return left;
}
static int lower_bound(int x, List<Integer> v)
{
if(v == null) return 0;
int left = 0;
int right = v.size();
while(left < right)
{
int mid = (left + right) / 2;
if(x > v.get(mid)) left = mid + 1;
else right = mid;
}
return left;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
StringBuilder sb = new StringBuilder();
Map<Integer, List<Integer>> posx = new HashMap<>();
Map<Integer, List<Integer>> posy = new HashMap<>();
Set<pair> s = new HashSet<>();
int n = Integer.parseInt(br.readLine());
for(int i=0; i<n; i++)
{
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
posx.putIfAbsent(x, new ArrayList<>());
posx.get(x).add(y);
posy.putIfAbsent(y, new ArrayList<>());
posy.get(y).add(x);
s.add(new pair(x, y));
}
for(Integer i : posx.keySet()) Collections.sort(posx.get(i));
for(Integer i : posy.keySet()) Collections.sort(posy.get(i));
int p = Integer.parseInt(br.readLine());
for(int i=0; i<p; i++)
{
st = new StringTokenizer(br.readLine());
int x1 = Integer.parseInt(st.nextToken());
int y1 = Integer.parseInt(st.nextToken());
int x2 = Integer.parseInt(st.nextToken());
int y2 = Integer.parseInt(st.nextToken());
int ans = 0;
ans += upper_bound(y2, posx.get(x1)) - lower_bound(y1, posx.get(x1));
ans += upper_bound(y2, posx.get(x2)) - lower_bound(y1, posx.get(x2));
ans += upper_bound(x2, posy.get(y1)) - lower_bound(x1, posy.get(y1));
ans += upper_bound(x2, posy.get(y2)) - lower_bound(x1, posy.get(y2));
if(s.contains(new pair(x1, y1))) ans--;
if(s.contains(new pair(x1, y2))) ans--;
if(s.contains(new pair(x2, y1))) ans--;
if(s.contains(new pair(x2, y2))) ans--;
sb.append(ans).append("\n");
}
System.out.println(sb);
}
}
