문제 링크
문제
티어: 골드 2
알고리즘: 정렬, 우선순위 큐, 자료구조
집과 사무실을 통근하는 n명의 사람들이 있다. 각 사람의 집과 사무실은 수평선 상에 있는 서로 다른 점에 위치하고 있다. 임의의 두 사람 A, B에 대하여, A의 집 혹은 사무실의 위치가 B의 집 혹은 사무실의 위치와 같을 수 있다. 통근을 하는 사람들의 편의를 위하여 일직선 상의 어떤 두 점을 잇는 철로를 건설하여, 기차를 운행하려고 한다. 제한된 예산 때문에, 철로의 길이는 d로 정해져 있다. 집과 사무실의 위치 모두 철로 선분에 포함되는 사람들의 수가 최대가 되도록, 철로 선분을 정하고자 한다.
양의 정수 d와 n 개의 정수쌍, (hi, oi), 1 ≤ i ≤ n,이 주어져 있다. 여기서 hi와 oi는 사람 i의 집과 사무실의 위치이다. 길이 d의 모든 선분 L에 대하여, 집과 사무실의 위치가 모두 L에 포함되는 사람들의 최대 수를 구하는 프로그램을 작성하시오.
그림 1 에 있는 예를 고려해보자. 여기서 n = 8, (h1, o1) = (5, 40), (h2, o2) = (35, 25), (h3, o3) = (10, 20), (h4, o4) = (10, 25), (h5, o5) = (30, 50), (h6, o6) = (50, 60), (h7, o7) = (30, 25), (h8, o8) = (80, 100)이고, d = 30이다. 이 예에서, 위치 10 과 40 사이의 빨간색 선분 L이, 가장 많은 사람들에 대하여 집과 사무실 위치 모두 포함되는 선분 중 하나이다. 따라서 답은 4 이다.
입력
입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,000이하의 서로 다른 정수이다. 마지막 줄에, 철로의 길이를 나타내는 정수 d (1 ≤ d ≤ 200,000,000)가 주어진다.
출력
출력은 표준출력을 사용한다. 길이 d의 임의의 선분에 대하여, 집과 사무실 위치가 모두 그 선분에 포함되는 사람들의 최대 수를 한 줄에 출력한다.
풀이
선분에 포함되는 사람들의 최대 수를 출력해야 한다.
hi >= oi라고 했을 때 오름차순으로 정렬해 본다.
hi가 가장 앞에 있는 선을 먼저 포함한다고 했을 때 선분 L의 시작 지점을 hi와 맞춰주는 것이 현재 선분을 포함할 수 있는 가능성도 높일 수 있고, 다른 hi_oi 선분도 포함할 가능성이 높아진다.
그래서 가장 앞에 있는 hi와 선분 L을 맞춰줬을 때 L의 끝은 hi + L의 길이가 되며 이것을 end라고 부르겠다.
end보다 작거나 같은 모든 oi를 카운트 해준다. 현재는 가장 앞에 있는 hi를 기준으로 했기 때문에 뺄 값이 없다.
그리고 다음으로 큰 hi로 넘어가는데 이를 h2라고 하겠다. 다음 end는 h2 + L이 되고,
end보다 작거나 같은 모든 oi를 카운트 해준다. 그런데 h1이 현재 end에 포함되어 있다면, 그 값은 포함되어서는 안된다. 출발점이 L 선분에 포함되어 있지 않기 때문이다.
그래서 h1_L+h1의 포함된 사람의 수를 구했다면, 이후 h2를 기준으로 했을 때는 end가 더 커지기 때문에 현재 end (L + h1)보다 작거나 같으면 sub에 +1를 해준다.
그러면 이후에 h2_L+h2의 포함된 사람의 수를 구할 때는 L+h2보다 작은 o1의 사람의 개수를 구하고, h1으로 시작하는 사람은 sub에 더해줬기 때문에 sum - sub가 된다.
다른 경우도 있다.
h1o1이 현재 end를 벗어나는 경우다. 이 경우에 sub를 +1 해준다면 더해지지도 않았는데 빼는 문제가 발생한다.
이를 해결하기 위해서 map을 활용해서 h1o1이 포함될 시점에 sub가 더해지게끔 해준다.
그러면 정확한 sum - sub를 구할 수 있고, 이 중 큰 값을 출력하면 된다.
이제는 이 풀이를 어떻게 구현할 것인지 고민해 봐야 한다.
나는 HashMap과 우선순위 큐, ArrayList, 정렬, 누적합?을 활용해서 풀었다.
일단 h1은 중복되어서는 안된다. 중복 없이 h1을 모아서 오름차순 정렬해주면, 앞에서부터 차례대로 L선분의 시작 지점이 된다.
end보다 작거나 같은 o1을 구할 때는 우선순위 큐를 활용했다. 우선순위 큐를 o1을 기준으로 오름차순 정렬하고, peek를 통해 end보다 작거나 같은 사람을 poll()해주면 된다.
그리고 그만큼 sum을 더해주는데, 여기서 중요한 점은 현재 사람의 o1이 L의 출발지점보다 작은 경우는 sub에 더해줘야 한다는 것이다. (포함되지 않기 때문에 빼야할 값임)
그래서 이 경우 map을 활용할 수 있다. map으로 end보다 큰 경우에는 o1을 키로 vlaue를 +1씩 추가해 주면 poll()을 했을 때 그러니까 end에 포함되었을 때 출발지점이 포함되지 않은 사람을 빼줄 수 있다.
그런데 만약 현재 end보다 작거나 같은 경우 (이미 포함된 경우)는 미리 sub에 더해주면 된다. 이미 sum에 포함되어 있고, 이 sum 값은 다음 경우에도 이어지기 때문이다.
그 코드는 다음과 같다.
ArrayList<Integer> curOList = hMap.get(hList.get(i));
for(int j=0; j<curOList.size(); j++) {
if(curOList.get(j) <= end) {
//이미 포함되어 있는 경우
sub += 1;
continue;
}
//end를 벗어나는 경우 나중에 end가 포함될 때 sub에 ++
if(sMap.get(curOList.get(j)) == null) {
sMap.put(curOList.get(j), 0);
}
sMap.put(curOList.get(j), sMap.get(curOList.get(j)) + 1);
}그리고 poll할 때 체크해 주는 것이다.
int end = hList.get(i) + L; //출발지점 + L
while(!pq.isEmpty()) {
if(pq.peek().o > end) {
break;
}
Person p = pq.poll();
if(sMap.get(p.o) != null) {
sub += sMap.get(p.o);
sMap.put(p.o, 0);
}
sum += 1;
}이런 식으로 풀이를 구현할 수 있다.
소스 코드
import java.io.*;
import java.util.*;
class Person implements Comparable<Person> {
int h, o;
Person(int h, int o) {
this.h = h;
this.o = o;
}
@Override
public int compareTo(Person o) {
if(this.o < o.o) {
return -1;
} else if(this.o > o.o) {
return 1;
}
return 0;
}
}
public class Main {
static int N, L;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
HashMap<Integer, ArrayList<Integer>> hMap = new HashMap<>();
PriorityQueue<Person> pq = new PriorityQueue<>();
for(int i=0; i<N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int h = Math.min(a, b);
int o = Math.max(a, b);
pq.add(new Person(h, o));
if(hMap.get(h) == null) {
hMap.put(h, new ArrayList<>());
}
hMap.get(h).add(o);
}
L = Integer.parseInt(br.readLine());
ArrayList<Integer> hList = new ArrayList<>();
for (Integer key: hMap.keySet()) {
hList.add(key);
}
Collections.sort(hList, new Comparator<Integer>() {
@Override
public int compare(Integer a, Integer b) {
return Integer.compare(a, b);
}
});
int answer = -1;
int sum = 0;
int sub = 0;
HashMap<Integer, Integer> sMap = new HashMap<>();
for(int i=0; i<hList.size(); i++) {
int end = hList.get(i) + L; //출발지점 + L
while(!pq.isEmpty()) {
if(pq.peek().o > end) {
break;
}
Person p = pq.poll();
if(sMap.get(p.o) != null) {
sub += sMap.get(p.o);
sMap.put(p.o, 0);
}
sum += 1;
}
answer = Math.max(answer, sum - sub);
ArrayList<Integer> curOList = hMap.get(hList.get(i));
for(int j=0; j<curOList.size(); j++) {
if(curOList.get(j) <= end) {
//이미 포함되어 있는 경우
sub += 1;
continue;
}
//end를 벗어나는 경우 나중에 end가 포함될 때 sub에 ++
if(sMap.get(curOList.get(j)) == null) {
sMap.put(curOList.get(j), 0);
}
sMap.put(curOList.get(j), sMap.get(curOList.get(j)) + 1);
}
}
System.out.println(answer);
}
}