1. 문제설명
n개의 도시가 1 ~ n번으로 일렬로 배치되어 있다.
지수는 연속한 K개의 도시에 대하여 소득이 가장 높은 도시와 가장 낮은 도시의 소득 차가 일정이상이 되면 이 K개의 도시가 속한 영역을 불안전 지역이라고 정의
ex) n = 7, k = 3 / [10, 2, 5, 3, 7, 9, 1]
이 중 1~3번 도시가 포함된 영역과 5~7번 도시가 포함된 영역은 최고 소득과 최저 소득의 차가 8이므로 문제의 정답이 된다. 반면에 2~4번 도시가 포함된 영역에서는 최고와 최저 소득 차가 3이므로 앞의 두 영역에 비해서 작다.
N개의 도시에 대한 소득 수준이 입력으로 주어질 때 동서로 연속한 K개의 도시를 포함하는 영역들 중 가장 큰 소득차를 가지는 영역의 소득차이를 계산하는 프로그램을 작성하시오.
입력 형식
첫 줄에는 테스트케이스의 수를 나타내는 10이하의 자연수 T가 주어진다. 이후 총 T개의 테스트케이스에 대한 입력이 차례로 주어진다.
각 테스트케이스의 첫 줄에는 두 개의 자연수가 공백으로 구분되어 N K형식으로 주어진다.
N은 도시의 수를 나타내는 20만이하의 자연수다.
K는 한 조사 영역이 포함하는 연속한 도시의 수를 나타내는 N이하의 자연수다.
각 테스트케이스의 두 번째 줄에는 각 도시의 소득 수준을 나타내는 N개의 자연수가 차례로 공백으로 구분되어 주어진다.
1번 도시부터 N번 도시까지의 소득 수준이 순서대로 주어진다.
입력되는 숫자는 모두 10억이하의 자연수이며 각각 공백으로 구분되어 있다.
출력 형식
각 테스트케이스에 대한 정답을 한 줄씩 출력한다.
연속한 K개의 도시로 이루어진 영역들 중 가장 큰 소득차를 가지는 영역의 소득차를 출력한다.
2. 알고리즘 접근
연속한 K개의 데이터 접근 -> Sliding Window 고려
but 최대값과 최소값에 대한 갱신이 쉽지 않다
-> 삭제되는 값이 최대값 or 최소값이라면 최대 최소를 윈도우마다 다시 찾아야함
최대, 최소 문제 시 고려사항
- 정렬을 이용한 방법
- binary search tree(정렬 기반의 자료구조)
- priority Queue(우선순위 큐)
Priority Queue를 이용해서 풀어보자
Priority Queue 사용 시 문제 사항
- 우선순위는 1개만 가능하다 -> 최대값, 최소값 두가지의 기준 존재
-> 그러나 이는 Priority Queue를 그냥 두개 쓰면 해결된다 - 큐에서 원하는 원소의 삭제가 어렵다
문제 해결 아이디어
슬라이딩 윈도우를 이용해 풀려고 하니 윈도우마다 다시 찾아야한다
-> 슬라이딩 윈도우를 이용해 갱신할 때 큐 내의 데이터를 꼭 항상 삭제해야할까??
-> ex) [7, 10, 11, 15]의 경우 큐에 (7, 10, 11, 15)가 저장하고 7은 최대값을 해치지 않기에 굳이 바로 삭제할 필요가 없다.
불필요한 범위의 원소가 해당 범위의 최대/최소가 아니라면 영향을 미치지 않는다.
즉, 불필요한 숫자가 최대/최소가 되면 그 때 제거하고 최대/최소를 구하자
3. 소스코드
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Scanner;
public class Q5G {
public static final Scanner sc = new Scanner(System.in);
private static int getMaximumRangeDifference(int n, int k, City[] cities) {
int answer = 0;
// 소득이 가장 작은 도시부터 POP되는 우선순위 큐
PriorityQueue<City> rangeMinimum = new PriorityQueue<>();
// 소득이 가장 큰 도시부터 POP되는 우선순위 큐
PriorityQueue<City> rangeMaximum = new PriorityQueue<>(Collections.reverseOrder()); // 우선순위 뒤집기
// 슬라이딩 윈도우
for(int i = 0; i < n; i++){
City c = cities[i];
int rightEnd = i; // 윈도우의 마지막 원소 i
int leftEnd = i - k + 1; // 윈도우의 첫 원소
rangeMaximum.add(c); // 큐에 값 추가
rangeMinimum.add(c); // 큐에 값 추가
// 윈도우를 벗어난 원소 삭제 -> MIN, MAX에 영향을 주는 원소만 삭제
// 큐가 비어있지 않고, 큐의 최대값 인덱스가 윈도우 밖이라면
// 10 2 5 3 7 9 1
while (rangeMaximum.size() > 0 && rangeMaximum.peek().index < leftEnd) {
rangeMaximum.poll();
}
while (rangeMinimum.size() > 0 && rangeMinimum.peek().index < leftEnd){
rangeMinimum.poll();
}
// rangeMaximum과 rangeMinimum에는 결과에 영향을 주는 윈도우 밖의 결과는 삭제됨 \
if(leftEnd < 0){
continue; // 윈도우가 음수인덱스라면 건너뛴다
}
int maximum = rangeMaximum.peek().income;
int minimum = rangeMinimum.peek().income;
int diff = maximum - minimum;
answer = Math.max(answer, diff);
}
return answer;
}
private static void testCase(int caseIndex) {
int n = sc.nextInt(); // 도시의 수 n
int k = sc.nextInt(); // 조사의 영역 k (윈도우 범위)
City[] cities = new City[n];
for(int i = 0; i < n; i++){
int income = sc.nextInt();
cities[i] = new City(i, income);
}
int answer = getMaximumRangeDifference(n, k, cities);
System.out.println(answer);
}
public static void main(String[] args) {
int caseSize = sc.nextInt();
for(int caseIndex = 1; caseIndex <= caseSize; caseIndex++){
testCase(caseIndex);
}
}
}
class City implements Comparable<City>{
public final int index; // 해당 도시의 인덱스
public final int income; // 해당 도시의 소득
City(int index, int income){
this.index = index;
this.income = income;
}
@Override
public int compareTo(City o) {
// 소득에 대한 우선순위를 가지도록 대소관계 정의
return this.income - o.income;
}
}
