[백준/BOJ] 백준 1306번 : 달려라 홍준

www.acmicpc.net/problem/1306

1306번: 달려라 홍준

map을 이용한 슬라이딩 윈도우를 이용해 문제를 해결했다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <map>
using namespace std;

int n, m;
vector<int> ad(1000001);
map<int, int> see; //(빛의 세기, 개수)
map<int, int>::iterator it;
vector<int> result;

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

	cin >> n >> m;

	for (int i = 1; i <= n; i++)
	{
		int input;
		cin >> input;

		ad[i] = input;
	}

	for (int i = 1; i <= (2 * m) - 1; i++)
	{
		if (i > n)
			break;

		if (see.count(ad[i]) != 0)
			see[ad[i]]++;
		else
			see.insert(make_pair(ad[i], 1));
	}

	it = see.end();
	it--;
	result.push_back((*it).first); //see에 저장된 값중 가장 큰 값 저장

	for (int i = m + 1; i <= n - m + 1; i++)
	{
		int left = i - (m - 1);
		int right = i + (m - 1);

		//움직이면서 시야에서 벗어나는값 제거
		see[ad[left - 1]]--;
		if (see[ad[left - 1]] == 0)
		{
			it = see.lower_bound(ad[left - 1]);
			see.erase(it);
		}

		//움직이면서 시야에 들어오는값 저장
		if (see.count(ad[right]) != 0)
			see[ad[right]]++;
		else
			see.insert(make_pair(ad[right], 1));

		it = see.end();
		it--;
		result.push_back((*it).first); //see에 저장된 값중 가장 큰 값 저장
	}

	for (int i = 0; i < result.size(); i++)
		cout << result[i] << " ";

	return 0;
}