[1306] 달려라 홍준 - Java[자바]

 

 

 

| 문제 링크

 

 

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

1306번: 달려라 홍준

 

 

 

 

---

 

 

 

 

| 문제

 

 

1. 달리기 위한 코스 길이 N과 시야 범위 M이 주어집니다. (1 ≤ M ≤ N ≤ 1,000,000)
2. M번 위치부터 N-M+1번 위치까지 일정한 속도(1칸씩 이동)로 달리며, 달리는 위치에서 왼쪽으로 M-1번 칸 부터 오른쪽으로 M-1번 칸 까지 중 밝기가 가장 강한 간판이 보입니다.
3. N개의 간판의 밝기가 주어졌을 때, 매 칸마다 보이는 간판의 밝기를 출력하시오.

 

 

 

 

---

 

 

 

 

| 풀이

 

 

1. 구간의 최대값을 여러번 구하는 문제로 세그먼트 트리를 이용해 풀었습니다.
2. 완전 이진 트리의 형태로 세그먼트 트리를 만들기 위해, 2^k>=n 을 만족하는 자연수 k를 구하고 사이즈가 2^(k+1)인 세그먼트 트리를 만들어줍니다.
3. 완전 이진 트리 형태의 세그먼트 트리로 루트 노드는 모든 리프 노드의 정보를 가지고 있으며, 해당 노드에 포함된 리프 노드들의 첫 노드를 s 마지막 노드를 e라고 했을 때, 왼쪽 자식은 s~mid(=(s+e)/2) 리프 노드, 오른쪽 자식은 mid+1~e 리프 노드의 정보를 가지고 있습니다.
4. 이러한 특색을 이용해 리프 노드(sign의 밝기)에 해당하는 세그먼트 트리의 노드에는 리프 노드 값을 넣어주고, 이외의 노드들에는 자식 노드들 중 최대값(즉 노드에 포함된 리프 노드들 중 최대 값)을 입력합니다.
5. 반복문을 통해 m번 칸부터, n-m+1 칸까지 한 칸씩 나아가며, 세그먼트 트리를 조회합니다.
6. 세그먼트 트리의 루트 노드부터 탐색을 시작하며, 시야에 포함되는 범위와 세그먼트 트리의 노드들마다 포함하고 있는 리프 노드(sign의 밝기)의 범위를 비교해 다음과 같이 동작해줍니다.
   
   1) 세그먼트 트리 노드의 리프 노드 범위가 시야의 범위를 완전히 벗어나는 경우: 0을 반환
   2) 세그먼트 트리 노드의 리프 노드 범위가 시야의 범위에 완전히 포함되는 경우: 해당 노드 값을 반환
   3) 세그먼트 트리 노드의 리프 노드 범위가 시야의 범위에 일부 걸친 경우: mid를 기준으로 재탐색 후 max값을 반환

 

 

 

하기 코드에 주석을 작성해 놓았으니 이해에 도움이 되었으면 좋겠습니다.

 

 

---

 

 

 

 

| 코드

 

 

import java.io.*;
import java.util.StringTokenizer;

public class Main {
	
	public static int[] sign;
	public static int[] tree;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		//0번째 인자는 사용하지 않음, default 0
		sign = new int[n+1];
		st = new StringTokenizer(br.readLine());
		for(int i = 1; i<=n; i++) {
			sign[i] = Integer.parseInt(st.nextToken());
		}
		
		//세그먼트 트리 사이즈 구하기
		int k = (int) Math.ceil(Math.log(n)/Math.log(2)) + 1;
		int size = (int) Math.pow(2, k);
		
		tree = new int[size];
		
		//세그먼트 트리 리프노드에 배열 값 입력하며, 각 노드는 자식 노드들 중 최대값 입력
		init(1,n,1);
		//sign배열의 0번째 인자는 사용하지 않으므로 m부터 시작, i-(m-1), i+(m-i) 탐색
		for(int i = m; i<=n-m+1; i++) {
			sb.append(query(1,n,1,i-m+1,i+m-1)).append(" ");
		}
		bw.write(sb.toString());
		br.close();
		bw.close();
	}
	/*
	 * s: 리프노드의 시작점, sign배열의 인덱스에 해당
	 * e: 리프노드의 끝점, sign배열의 인덱스에 해당
	 * node: 세그먼트 트리의 루트를 기준으로 왼쪽 자식 노드는 s~mid((s+e)/2)의 sign 배열의 값을 가지고,
	 * 		 오른족 자식 노드는 mid+1~e의 sign 배열의 값을 가지고있음
	 * 완전 이진 트리로 왼쪽 자식은 node*2, 오른쪽 자식은 node*2+1
	 */
	public static int init(int s, int e, int node) {
		//리프노드에 해당한다면 해당 리프 노드에 sign 배열의 값을 입력
		if(s==e)
			return tree[node] = sign[s];
		//리프노드가 아니라면 왼쪽 자식과 오른쪽 자식 중 최대 값을 입력
		int mid = (s+e) >>> 1;
		return tree[node] = Math.max(init(s,mid,node*2), init(mid+1,e,node*2+1));
		
	}
	
	/*
	 * s: 리프노드의 시작점, sign배열의 인덱스에 해당
	 * e: 리프노드의 끝점, sign배열의 인덱스에 해당
	 * node: 세그먼트 트리의 루트를 기준으로 왼쪽 자식 노드는 s~mid((s+e)/2)의 sign 배열의 값을 가지고,
	 * 		 오른족 자식 노드는 mid+1~e의 sign 배열의 값을 가지고있음
	 * L: 탐색하고자 하는 시작 범위
	 * R: 탐색하고자 하는 끝 범위
	 */
	public static int query(int s, int e, int node, int L, int R) {
		//탐색 범위를 벗어나는 경우 0을 리턴
		if(R<s || e<L)
			return 0;
		//탐색 범위 안에 sign의 정보가 모두 포함된다면 해당 세그먼트 트리의 노드 값(자식들의 리프 노드 중 최대 값이 저장되어 있음)을 출력
		if(L<=s && e<=R)
			return tree[node];
		//범위에 일부만 걸친 경우 반으로 나누어(어느쪽인가는 범위를 벗어나 재귀를 통해 0으로 출력) max값을 비교
		int mid = (s+e) >>> 1;
		return Math.max(query(s,mid,node*2,L,R),query(mid+1,e,node*2+1,L,R));
	}

}