deque이 가능한 상황을 분석해본 내용은 아래와 같다.

  1. 구간이 있다.

    → front().idx와 비교해 pop_front()가 필요하다.

  2. 스택에 깊은 데이터부터 값이 내림차순으로 입력되도록 만들 수 있다.

    → 불필요한 중간 값을 버리고자 pop_back()이 필요하다.

    → front()가 최댓값이 된다.

  3. push_front()가 없어야 하는 건지 없어도 되는 건지 아직은 모르겠는데, 깔끔하게 유지하려면 push_back()을 쓰는 것이 논리에 맞기에 push_front()는 쓰지 않도록 한다.

알고리즘 템플릿

long long solve() {
	int num;
	cin >> num;

	long long result = num;
	DQ.push_back({ num, 0 }); // 가장 마지막에 항상 push가 있어
														// 흐름을 통일하고자 첫번째 데이터를 넣는다.
	for (int i = 1; i < N; ++i) {
		cin >> num;
		if (i - DQ.front().idx > D) { // 반복할 때마다 index는 1개씩 추가되고 front()에 
																	// push_front()로 다른 index의 값이 끼어들지 않기 때문에
																	// if문이 true인 경우는 매반복시 반드시 1개 이하이다.
			DQ.pop_front();
		}
	
		long long curSumScore = max(0LL, DQ.front().score) + num; // front().score가 음수라면, num부터 새로 시작
																															// front().score가 양수라면, 여기에 누적해 계산
		while (DQ.empty() == false && curSumScore >= DQ.back().score) { // 최댓값을 구하기 위해 
																																		// DQ 내에 내림차순으로 유지
			DQ.pop_back();
		}
		
		DQ.push_back({ curSumScore, i }); // 가장 마지막엔 이번에 비교한 데이터를 push
	
		result = max(result, curSumScore); // global ans를 갱신한다.
	}
	
	return result;
}

문제 및 풀이

🌟 연세워터파크 (https://www.acmicpc.net/problem/15678)

우선순위 큐를 사용해 top의 값과 nums[i]의 값의 부호를 비교해 손쉽게 구할 수 있었다.

그런데 코드를 짜면서 보니, 큐에 노드의 개수가 왠지 1개일 때가 많은 것 같고, 컴팩트하게 들어가는 데이터를 줄일 수 있을 것 같았다. → 덱을 사용해 구간 최댓값을 개선할 수 있었다.

처음에는 if문으로 deque의 front가 양수인지 아닌지, 새로운 수인 num이 양수인지 아닌지의 분기를 나누어 계산했으나, front가 음수일 땐 front를 쓰지 않고 0을 쓰는 걸로 하고, num은 양수라면 결국 deque을 모두 비우게 되고, 양수가 아니라면 스택처럼 유지하게 만들기 때문에 분기가 필요 없게 되어 반복문만 사용하는 일반화된 코드가 가능했다.