최솟값 찾기

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2.4 초 (하단 참고)

512 MB

42084

13086

8592

30.747%

문제

N개의 수 A1, A2, ..., AN과 L이 주어진다.

Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다.

입력

첫째 줄에 N과 L이 주어진다. (1 ≤ L ≤ N ≤ 5,000,000)

둘째 줄에는 N개의 수 Ai가 주어진다. (-109 ≤ Ai ≤ 109)

출력

첫째 줄에 Di를 공백으로 구분하여 순서대로 출력한다.

deque를 활용해 문제를 해결했다. 여기서 Node라는 key와 value를 담을 수 있는 클래스로 구현했다.

#include <iostream>
#include <deque>

using namespace std;

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

	int size = 0;
	int range = 0;
	typedef pair<int, int> Node;
	deque<Node> list;

	cin >> size >> range;

	for (int i = 1; i <= size; i++)
	{
		int target;

		cin >> target;

		while (list.size() >= 1 && list.back().second > target)
		{
			list.pop_back();
		}

		list.push_back(Node(i, target));

		if (i - list.front().first >= range)
		{
			list.pop_front();
		}

		cout << list.front().second << " ";
	}
}

Node의 first에는 인덱스 값이, second에는 데이터가 들어가도록 한다.

while (list.size() >= 1 && list.back().second > target)
{
	list.pop_back();
}

데이터를 넣기전 현재 값보다 높은 데이터가 있다면 뒤에서 부터 지워주도록 하는 while문을 만든다.

if (i - list.front().first >= range)
{
	list.pop_front();
}

deque에 range를 넘어갔는지 조건을 걸어 넘어갔다면 가장 앞에 있는 데이터를 날린다.