BOJ 백준 18277 Bliski Brojevi

 

문제 : https://www.acmicpc.net/problem/18277

 

[ 문제 요약 ]

• 접시 N 개의 더미가 있고, 1번 더미는 1개, 2번은 2개, N 번 더미는 N 개의 접시가 있습니다. 이 더미들의 위치를 섞고 Q 개의 질문에 답합니다.
• L 번째 더미와 R 번째 더미 사이에 있는 어떤 두 더미의 접시 수 차이의 최솟값은 얼마인가요? ( min{L <= i < j <= R}| pi - pj |

 

[ 테스트 케이스 요약 ]

7 5// 자연수 개수(1<=30,000), 쿼리 수(1<=30,000)
5 2 3 6 1 4 7// N이하 자연수가 고유하게 주어짐
3 5
5 7
1 2
3 6
2 7
//답
2
3
3
1
1

 

 

[ 알고리즘 분류 ]

• 자료 구조
• 세그먼트 트리
• 오프라인 쿼리
• Mo’s 알고리즘

 

[ 문제 해설 ]

 

문제 해설은 두가지 코드를 제시합니다. 두번 째 코드가 좀더 짧고 빠릅니다.

 

차이가 가장 작다는 것은 두 숫자가 가깝다는 것을 의미합니다. 이를 빠르게 구하기 위해 최대 값 세그먼트 트리와 최솟값 세그먼트 트리를 준비합니다.

 

세그먼트 트리의 index는 해당 숫자 자체를 의미하고, 안에 저장된 value도 해당 숫자 자체를 담고 있으면 됩니다.

 

그리고 값의 차이를 인덱스로 담을 카운팅 배열인 cnt를 준비합니다. cnt 배열은 해당 차이가 몇 번 등장했는지를 value로 갖고 있습니다. 또한, 결국 답은 최소 차이를 출력해야 하는 것인데, 가장 작은 최소 차이를 cnt 배열에서 완전 탐색하면 시간 초과이기 때문에 cnt 배열을 제곱근 분할로 나눠 표현할 fac 배열도 준비합니다.

 

이렇게 세그먼트 트리를 이용해 자기보다 큰 값중 가장 작은 것, 자기보다 작은 값중 가장 큰 것을 구해오고 각각의 차이를 카운팅 배열에 실시간으로 갱신하며, 마지막에 fac 배열과 cnt 배열 탐색을 통해 가장 작은 값의 차이를 출력해 주면 됩니다.

 

쿼리가 여러 개이기 때문에 쿼리 또한 Mo’s 알고리즘으로 정렬한 후 풉니다.

 

• [ 특정수가 추가될 때 ]
  • 나보다 큰 수 중 최솟값 구하기 : 최솟값 세그먼트 트리를 통해 나를 초과하는 범위 중 가장 작은 것을 구함
  • 나보다 작은 수 중 최댓값 구하기 : 최댓값 세그먼트 트리를 통해 나보다 작은 범위 중 가장 큰 것을 구함
  • 이렇게 하면 추가되는 수와 가장 가까운 큰 수, 작은 수를 알 수 있게 그에 따른 치이도 모두 알 수 있어, 해당 차이를 카운팅 배열과 제곱근 배열에 마킹합니다.
• [ 특정수가 삭제될 때 ]
  • 나보다 큰 수 중 최솟값 구하기 : 최솟값 세그먼트 트리를 통해 나를 초과하는 범위 중 가장 작은 것을 구함
  • 나보다 작은 수 중 최댓값 구하기 : 최댓값 세그먼트 트리를 통해 나보다 작은 범위 중 가장 큰 것을 구함
  • 수가 추가될 때와 마찬가지로 카운팅 배열과 제곱근 배열에 마킹
• [ 최종 답 구하기 ]
  • 제곱근 분할 배열 fac에서 값이 1 이상인 구간을 찾아내기 위해 작은 수부터 큰 수로 돌며 찾고, 찾은 후 그 구간의 범위를 카운팅 배열에서 작은 수 → 큰 수 방향으로 탐색해 가장 작은 차이를 출력합니다.

 

추가적인 문제는, 카운팅 배열에 큰 수와 작은 수 차이 값을 업데이트할 때, 어떻게 업데이트를 하는지가 중요합니다.

 

숫자 X를 추가할 때, X보다 작은 값이 A, 큰값이 B라고 하면,

 

A —— B였던 모양에서,

A —— X —— B 모양으로 변경됩니다.

 

그럼 원래 A-B 값의 차이가 카운팅 배열 cnt에 있을 테니, 그 값을 먼저 삭제하고, A와 X의 차이 + B와 X의 차이를 각각 카운팅 배열 cnt에 넣어줍니다.

 

특정수 X를 삭제할 때는 반대로, A와 X의 차이 + B와 X의 차이를 각각 카운팅 배열에서 제거해 주고, A-B의 차이를 카운팅 배열 원복 해 줍니다.

 

이로써 카운팅 배열에는 완전하게 모든 원소의 차이 값이 들어가 있을 수 있게 됩니다.

 

[ 정답 코드(1) ]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

class Main{
	
	static final int INF = 1<<30;
	static int sqrt;
	static int N, Q;
	static int ans[];// 최종 결과를 담을 배열
	static int arr[];// 입력된 더미의 초기값을 받을 배열
	static int cnt[];// 차이가 나올 때마다 마킹할 카운팅 배열(차이는 최대 N만큼 가능)
	static int fac[];// 차이의 구간을 마킹할 제곱근 배열
	static Min_Seg minSeg;
	static Max_Seg maxSeg;
	static List<Query> query;
	
	public static void main(String[] args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());// 자연수 개수(1<=30,000)
		Q = Integer.parseInt(st.nextToken());// 쿼리 수(1<=30,000)
		sqrt = (int)Math.sqrt(N);
		arr = new int[N + 1];
		cnt = new int[N + 1];
		ans = new int[Q + 1];
		fac = new int[N / sqrt + 1];
		minSeg = new Min_Seg(N, INF);
		maxSeg = new Max_Seg(N);
		query = new ArrayList<>();
		
		st = new StringTokenizer(br.readLine());
		for(int i=1; i<=N; i++)
			arr[i] = Integer.parseInt(st.nextToken());// N이하 자연수가 고유하게 주어짐
		
		for(int i=1; i<=Q; i++)
		{
			st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			query.add(new Query(s, e, i, s / sqrt));
		}
		
		Collections.sort(query);
		
		int s = 1;
		int e = 0;
		
		for(Query q : query)
		{
			while(e < q.e) plus(arr[++e]);
			while(q.s < s) plus(arr[--s]);
			while(q.e < e) minus(arr[e--]);
			while(s < q.s) minus(arr[s++]);

			ans[q.idx] = find();
		}
		
		StringBuilder sb = new StringBuilder();
		
		for(int i=1; i<=Q; i++)
			sb.append(ans[i]).append('\n');
		
		System.out.print(sb);
	}
	static void plus(int num) {
		maxSeg.update(1, 1, N, num, num);
		minSeg.update(1, 1, N, num, num);
		// num보다 작은 것중 가장 큰것
		int min = maxSeg.query(1, 1, N, 1, num - 1);
		// num보다 큰 것중 가장 작은 것
		int max = minSeg.query(1, 1, N, num + 1, N);
		// 둘이 유효한 값이면 해당 값을 배열에서 지움, 이 유는, 둘 사이에 num이 들어갈 것이기 때문
		if(max != INF && min != 0)
			setDiff(max - min, -1);
		// max가 유효하면 num과 차이 삽입
		if(max != INF)
			setDiff(max - num, 1);
		// min이 유효하면 num과 차이 삽입 
		if(min != 0)
			setDiff(num - min, 1);
	}
	static void minus(int num) {
		maxSeg.update(1, 1, N, num, 0);
		minSeg.update(1, 1, N, num, INF);
		// num보다 작은 것중 가장 큰 것
		int min = maxSeg.query(1, 1, N, 1, num - 1);
		int max = minSeg.query(1, 1, N, num + 1, N);
		// 값이 유효하면 둘 사이 차이 복원
		if(max != INF && min != 0)
			setDiff(max - min, 1);
		// num과의 차이 삭제
		if(max != INF)
			setDiff(max - num, -1);
		// num과의 차이 삭제
		if(min != 0)
			setDiff(num - min, -1);
	}
	static void setDiff(int diff, int plus) {
		if(diff <= 0)// 차이가 0 이하인 것은 스킵
			return;
		// 차이와, 해당 구간에 값을 연산
		cnt[diff] += plus;
		fac[diff / sqrt] += plus;
	}
	static int find() {
		for(int i=0; i<=N / sqrt; i++)
		{
			if(fac[i] == 0)
				continue;
			
			int s = i * sqrt;
			int e = Math.min(s + sqrt - 1, N);
			while(s <= e)
			{
				if(cnt[s] != 0)
					return s;
				++s;
			}
		}
		return 0;
	}
}
class Min_Seg{
	final int INF;
	int N;
	int tree[];
	Min_Seg(int N, int INF)
	{
		this.N = N;
		this.INF = INF;
		this.tree = new int[N * 4];
		Arrays.fill(tree, INF);
	}
	public void update(int treeNode, int s, int e, int targetIdx, int value) {
		if(e < targetIdx || targetIdx < s)
			return;
		if(s == e)
		{
			tree[treeNode] = value;
			return;
		}
		
		int mid = (s + e) >> 1;
		
		update(treeNode << 1, s, mid, targetIdx, value);
		update(treeNode << 1 | 1, mid + 1, e, targetIdx, value);
		
		tree[treeNode] = Math.min(tree[treeNode << 1], tree[treeNode << 1 | 1]);
	}
	public int query(int treeNode, int s, int e, int left, int right)
	{
		if(e < left || right < s)
			return INF;
		
		if(left<=s && e<=right)
			return tree[treeNode];
		
		int mid = (s + e) >> 1;
		
		int L = query(treeNode << 1, s, mid, left, right);
		int R = query(treeNode << 1 | 1, mid + 1, e, left, right);
		
		return Math.min(L, R);
	}
}
class Max_Seg{
	int N;
	int tree[];
	Max_Seg(int N)
	{
		this.N = N;
		this.tree = new int[N * 4];
	}
	public void update(int treeNode, int s, int e, int targetIdx, int value)
	{
		if(e < targetIdx || targetIdx < s)
			return;
		if(s == e)
		{
			tree[treeNode] = value;
			return;
		}
		
		int mid = (s + e) >> 1;
		
		update(treeNode << 1, s, mid, targetIdx, value);
		update(treeNode << 1 | 1, mid + 1, e, targetIdx, value);
		
		tree[treeNode] = Math.max(tree[treeNode << 1], tree[treeNode << 1 | 1]);
	}
	public int query(int treeNode, int s, int e, int left, int right)
	{
		if(e < left || right < s)
			return 0;
		
		if(left<=s && e<=right)
			return tree[treeNode];
		
		int mid = (s + e) >> 1;
		
		int L = query(treeNode << 1, s, mid, left, right);
		int R = query(treeNode << 1 | 1, mid + 1, e, left, right);
		
		return Math.max(L, R);
	}
}
class Query implements Comparable<Query>{
	int s, e, idx, fac;
	Query(int s, int e, int idx, int fac){
		this.s=s;
		this.e=e;
		this.idx=idx;
		this.fac=fac;
	}
	@Override
	public int compareTo(Query o) {
		if(fac != o.fac)
			return fac - o.fac;
		if((fac & 1) == 0)
			return e - o.e;
		return o.e - e;
	}
}

 

 

[ 정답 코드(2) ]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

class Main{
	
	static int N, Q;
	static int arr[];
	static int ans[];
	static Node tree[];// 세그먼트 트리로 인덱스는 해당 자연수, value는 구간의 최솟값, 최댓값, 값 차이의 최솟값이 담김
	static List<Query> query;
	
	public static void main(String[] args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());// 자연수 개수(1<=30,000)
		Q = Integer.parseInt(st.nextToken());// 쿼리 수(1<=30,000)
		arr = new int[N + 1];
		ans = new int[Q + 1];
		tree = new Node[N * 4];
		query = new ArrayList<>();
		
		// 트리 초기화
		for(int i=N*4-1; i>=0; i--)
			tree[i] = new Node();
		
		st = new StringTokenizer(br.readLine());
		for(int i=1; i<=N; i++)
			arr[i] = Integer.parseInt(st.nextToken());
		
		for(int i=1, sqrt = (int)Math.sqrt(N); i<=Q; i++)
		{
			st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			query.add(new Query(s, e, i, s / sqrt));
		}

		Collections.sort(query);
		
		int s = 1;
		int e = 0;
		
		for(Query q : query)
		{
			while(e < q.e) update(1, 1, N, arr[++e], false);
			while(q.s < s) update(1, 1, N, arr[--s], false);
			while(q.e < e) update(1, 1, N, arr[e--], true);
			while(s < q.s) update(1, 1, N, arr[s++], true);
			
			ans[q.idx] = tree[1].diffMin; 
		}
		
		StringBuilder sb = new StringBuilder();
		
		for(int i=1; i<=Q; i++)
			sb.append(ans[i]).append('\n');
		
		System.out.print(sb);
	}
	
	static void update(int treeNode, int s, int e, int targetIdx, boolean isClear) {
		if(e < targetIdx || targetIdx < s)
			return;
		
		if(s == e)
		{
			// 초기화인경우
			if(isClear)
			{
				tree[treeNode].min = 1<<30;
				tree[treeNode].max = 0;
			}
			else// 초기화가 아니라 값 세팅인 경우 값 세팅
			{
				tree[treeNode].min = tree[treeNode].max = s;
			}
			return;
		}
		
		int mid = (s + e) >> 1;
		
		update(treeNode << 1, s, mid, targetIdx, isClear);
		update(treeNode << 1 | 1, mid + 1, e, targetIdx, isClear);
		
		merge(tree[treeNode], tree[treeNode << 1], tree[treeNode << 1 | 1]);
	}

	static void merge(Node origin, Node L, Node R) {
		int diff = 1<<30;
		
		if(R.min != 1<<30 && L.max != 0)
			diff = R.min - L.max;
		
		origin.min = Math.min(L.min, R.min);// 양쪽의 최솟 값 중 최솟 값
		origin.max = Math.max(L.max, R.max);//양쪽의 최댓 값 중 최댓 값
		origin.diffMin = Math.min(Math.min(L.diffMin, R.diffMin), diff);
	}
	static class Query implements Comparable<Query>{
		int s, e, idx, fac;
		Query(int s, int e, int idx, int fac){
			this.s=s;
			this.e=e;
			this.idx=idx;
			this.fac=fac;
		}
		@Override
		public int compareTo(Query o) {
			if(fac != o.fac)
				return fac - o.fac;
			
			if((fac & 1)==0)
				return e - o.e;
			
			return o.e - e;
		}
	}
	static class Node{
		int min;
		int max;
		int diffMin;
		Node(){
			this.min = 1<<30;
			this.max = 0;
			this.diffMin = 1<<30;
		}
		Node(int min, int max, int diffMin){
			this.min = min;
			this.max = max;
			this.diffMin = diffMin;
		}
	}
}

[ (2)코드 해설 ]

위 코드는 (1)코드 보다 간결하고 이해가 쉽습니다. 세그먼트 트리를 선언할 때 한 노드가 최솟값, 최댓값, 값 차이의 최솟값을 갖고있도록 만들면 됩니다.

 

세그먼트 트리의 리프노드 인덱스는 주어지는 각 숫자를 의미합니다. 주어지는 자연수의 최대가 3만이므로, 세그먼트 트리 리프노드 인덱스는 3만이하 입니다.

 

각 노드당 최솟값, 최댓값, 값 차이의 최솟값 을 갖고 있으면, 그 부모 노드에서도 왼쪽 자식노드, 오른쪽 자식노드를 통해 동일하게 최솟값, 최댓값, 값 차이의 최솟값을 구할 수 있습니다.

 

값 차이의 최솟값을 구할 때, 식은 아래와 같습니다.

 

min( L.diff, R.diff, R.min - L.max )

 

왼쪽 자식노드, 오른쪽 자식노드의 값 차이의 최솟값과, 오른쪽 자식노드의 가장 최솟값에서 왼쪽 자식노드의 가장 최댓값을 뺀 값의 min을 구하면 항상 값 차이의 최솟값을 유지할 수 있습니다.

 

이 부분을 이해하기 위해서는 손으로 그려서 따라해봐야 합니다. 리프 노드가 논리상 정렬된 상태로 쓰이도록 하기 때문에 성립함을 유념해야 합니다.