BOJ - 1306 ) 달려라 홍준

---

https://www.acmicpc.net/problem/1306

1306번: 달려라 홍준

 

---

길이가 N인 수열에서, 내가 현재있는 index 에서 [index-(M-1) ,  index+(M-1)] 에서 가장 큰 값을 찾으면 된다.

 

N = 100만 이므로, N^2의 풀이보다는 NlogN의 풀이인 세그먼트 트리를 이용하여,

 

N개의 쿼리를 처리해주자, 위문제는 O(NlogN+N) 에 처리가 가능하다.

 

즉, 구간의 최댓값을 저장하는 배열을 세그먼트 트리로 만들면 된다.

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.concurrent.SynchronousQueue;

public class Main {

	public static long seg[] , arr[];
	public static void main(String[] args) throws Exception {
	
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		arr = new long[n];
		for(int i=0;i<n;i++) {arr[i] = Long.parseLong(st.nextToken());}
		seg = new long[4*n];
		seginit(1,0,n-1);
		
		StringBuilder sb = new StringBuilder();
		
		for(int start=m-1 ; start <= n-m; start++) {
			sb.append(find(1,0,n-1,start-(m-1),start+(m-1))+" ");
		}
		
		System.out.print(sb);
	}
	private static long seginit(int node, int s, int e ) {
		if(s==e) {return seg[node]= arr[s];}
		int mid = (s+e)/2;
		return seg[node] = max (seginit(2*node ,s,mid) , seginit(2*node+1,mid+1, e));
	}
	private static long max(long a, long b) {
		return a >= b ? a : b;
	}
	private static long find(int node , int s , int e , int left , int right) {
		if(right < s || left > e) return -1;
		else if(left <= s && e <= right) {
			return seg[node];
		}
		else {
			int mid = (s+e)/2;
			return max(find(node*2 ,s, mid,left,right),find(node*2+1, mid+1 , e , left , right));
		}
	}
}

---

세그먼트 트리는 INDEX를 조심하자..