[P5] 백준 1306번 달려라 홍준 C++ 세그먼트 트리, 슬라이딩 윈도우

리뷰

 

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

세그먼트 트리 기본 + 슬라이딩 윈도우 기본, 플레티넘 문제 치고는 굉장히 쉬운 문제

 

 

전역 변수

• M : 광고판의 최대 개수를 저장할 정수형 상수 변수
• n : 주어지는 전광판의 개수를 저장할 변수
• m : 홍준이가 볼 수 있는 시야의 범위를 저장할 변수
• nodes : 주어지는 광고판의 빛의 세기를 저장하기 위한 정수형 배열
• tree : 세그먼트 트리 정보를 저장하기 위한 정수형 배열

 

함수

1. build

void build(int node, int s, int e)

 

최대값 세그먼트 트리 초기화를 위한 함수

1. 매개변수로 현재 노드 번호와 탐색 범위 s, e를 전달 받는다.
2. 기저 조건으로 만약 리프노드에 도달하였다면 현재 세그먼트 트리의 노드에 배열의 값을 저장해준다.
3. 리프노드가 아니라면 좌우 자식 노드로 재귀를 수행해준다.
4. 재귀를 빠져나오며 좌우 자식 노드 중 더 큰 값을 현재 노드의 값으로 저장해준다.

---

2. query

int query(int node, int s, int e, int L, int R)

 

최대값 세그먼트 트리에서 구간의 최대값을 구하기 위한 함수

1. 매개변수로 현재 노드 번호와 탐색 범위 s, e와 구간 범위 L, R을 입력받는다.
2. 만약 탐색 범위가 구간을 벗어났다면 0을 리턴해 준다.
3. 구간이 탐색 범위와 겹친다면 세그먼트 트리의 현재 노드에 저장된 값을 리턴해 준다.
4. 구간이 겹치지 않을 경우 좌우 노드로 재귀를 수행하고, 두 값 중 큰 노드의 값으로 리턴해 준다.

 

문제풀이

1. n, m값을 입력 받아주고, nodes배열에 n개의 광고판 빛의 세기 정보를 입력 받아준다.
2. build함수를 활용해 nodes배열을 기준으로 세그먼트 트리를 초기화 해준다.
3. m ~ n - m + 1범위까지 for문을 수행해 준다.
4. 각 루프마다 query함수를 통해 i - (m - 1) ~ i + (m - 1) 범위의 최대값을 구해 출력해 준다.
5. 각 출력값은 공백을 기준으로 구분한다.

 

트러블 슈팅

없음

 

 

참고 사항

없음

 

 

정답 코드

#include<iostream>
using namespace std;

const int M = 1e6 + 1;
int n, m;
int nodes[M];
int tree[M * 4];

void build(int node, int s, int e) {
	if (s == e) tree[node] = nodes[s];
	else {
		int mid = (s + e) / 2;
		build(node * 2, s, mid);
		build(node * 2 + 1, mid + 1, e);
		tree[node] = max(tree[node * 2], tree[node * 2 + 1]);
	}
}

int query(int node, int s, int e, int L, int R) {
	if (R < s || e < L) return 0;
	if (L <= s && e <= R) return tree[node];
	int mid = (s + e) / 2;
	return max(query(node * 2, s, mid, L, R), query(node * 2 + 1, mid + 1, e, L, R));
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m;
	for (int i = 1; i <= n; ++i) cin >> nodes[i];

	build(1, 1, n);

	for (int i = m; i <= n - m + 1; ++i) {
		cout << query(1, 1, n, i - (m - 1), i + (m - 1)) << " ";
	}
}