문제 링크
문제
티어: 골드 3
알고리즘: 그리디, 정렬, 스위핑
OJ시는 직선 형태의 가로수길에 총 N개의 가로등을 설치했다. 각 가로등의 위치는 지하철역을 기준으로 -1,000,000,000 이상 1,000,000,000 이하의 정수로 나타낼 수 있다. 한편, 모든 가로등은 자신과 L만큼 먼 곳까지 빛을 밝힐 수 있다. 예를 들어, 좌표가 5인 가로등이 2만큼 먼 곳까지 빛을 밝힐 수 있다면 좌표가 3~7인 곳을 밝힐 수 있다.
요즘 들어, OJ시에 전력난이 지속되어 자주 정전이 난다. 정전이 나면 가로수길이 완전히 암흑에 둘러싸이기 때문에 치안에 악영향을 끼친다. 따라서 OJ시에서 N개의 가로등들 중 일부를 비상용으로 전환해서 정전 시에만 켜지게 할 것이다.
평소의 조명 상태와 정전 시의 조명 상태가 균일하게 이루어져야 언제든지 시민들이 편하게 가로수길을 드나들 수 있다. 이에 따라 OJ시는 어떤 경우에도 항상 빛이 도달하는 지점의 총 길이를 최대화시키려고 한다. OJ시를 도와 무슨 가로등을 비상용으로 바꿀지 구하는 프로그램을 작성하여라.
입력
첫 번째 줄에는 가로등의 수 N과 가로등의 조도 L이 주어진다.
두 번째 줄에는 N개의 가로등의 좌표가 공백을 사이로 두고 차례대로 주어진다.
- 1 ≤ N ≤ 150,000
- 1 ≤ L ≤ 1,000,000,000
출력
가로등 중에 몇 개를 비상용으로 전환했을 때, 평상시와 비상시에 모두 빛의 영향을 받는 영역의 길이의 최댓값을 출력한다.
풀이
어떤 경우에도 항상 빛이 도달하는 지점의 총 길이를 최대화해야 한다.
그러니까 정전이 되든 되지 않든 항상 비추고 있는 영역을 최대화하는 것이다.
그 영역은 비상용 가로등과 기본 가로등이 동시에 비추는 영역이다.
그러면 어떤 가로등을 비상용 가로등으로 바꿔야 동시에 비추는 영역을 최대화할 수 있을까?
기본 가로등 사이에 모든 가로등을 비상용 가로등으로 바꾸는 것이 최선의 선택이 된다.
(여기서 가로등은 일자로 나열되어 있어야 한다. 오름차순 정렬)
예를 들어 x x x x x 일 때 2번 째와 4번 째 가로등을 비상용 가로등으로 바꾸면 동시에 비출 수 있는 가능성?을 최대로 할 수 있다. 물론 빛이 겹치는지는 확신할 수 없기 때문에 일단 가운데 가로등을 비상용으로 다 바꿔보는 것이다.
이 상태에서 우리는 빛이 겹치는 부분만을 계산하면 된다. 당연히 겹치지 않는 부분은 포함되서는 안된다.
계산 방법은 다음과 같다.
가로등의 좌표가 오름차순 정렬되어 있을 때 가운데 가로등을 비상용으로 바꾼 상태이다.
0번 째 인덱스부터 N - 2번 째 인덱스까지 차례대로 반복한다.
현재 가로등에서 비추는 max를 구하고, 다음 가로등에서 비추는 min을 구한다.
nextMin이 curMax보다 작다면 겹치는 부분이 존재하는 것이다.
그래서 curMax - nextMin을 더해준다.
이 겹치는 부분은 좌표이기 때문에 다음 가로등에서 계산될 때 포함되어서는 안된다. 그래서 last에 curMax를 저장한다. (curMax 이전에 비추는 영역은 다 구했기 때문에 중복되어서는 안됨)
다음 가로등을 계산할 때 last보다 nextMin이 작다면 중복 계산될 여지가 있다. 그래서 nextMin를 last로 변경해 준다.
이후에는 똑같이 겹치는 부분이 있는지 확인하고 겹치는 부분 포함하고, last 업데이트하고 반복해 주면된다. (모든 인덱스를 확인하는 이유는 가운데 가로등을 비상용으로 바꾸게 되면 각 가로등이 양 옆 가로등과 겹쳐질 가능성이 생기기 때문에 정말 겹쳐지는지 확인하는 과정이다.)
시간 복잡도는 O(N * logN)이다.
소스 코드
import java.io.*;
import java.util.*;
public class Main {
static int N;
static long L;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
L = Long.parseLong(st.nextToken());
long[] list = new long[N];
StringTokenizer st2 = new StringTokenizer(br.readLine());
for(int i=0; i<N; i++) {
list[i] = Long.parseLong(st2.nextToken());
}
Arrays.sort(list);
System.out.println(answer(list));
}
static long answer(long[] list) {
long cnt = 0;
long last = Long.MIN_VALUE;
for(int i=0; i<N -1; i++) {
long curMax = list[i] + L;
long nextMin = list[i + 1] - L;
if(nextMin < last) {
nextMin = last;
}
if(nextMin < curMax) {
cnt += curMax - nextMin;
last = curMax;
}
}
return cnt;
}
}