[백준 27527] 배너 걸기 (C++)

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

문제

---

현대오토에버는 현대자동차그룹의 모빌리티 소프트웨어 전문 기업으로서, In-Car와 Out-Car 영역 전반의 소프트웨어와 인프라를 안정적, 효율적, 혁신적으로 지원하는 'Mobility SW Provider' 역할을 수행하고 있다. 당신은 현대오토에버의 다양한 소프트웨어 기술을 선보이기 위한 행사를 준비하고 있으며, 행사는 현대오토에버 본사가 위치한 서울 삼성역 인근에서 개최될 예정이다.

이 행사를 홍보하기 위한 배너를 걸어야 하는데, 마침 당신은 현대오토에버의 MMS 기술을 사용하여 제작한 정밀 지도를 갖고 있다. MMS(Mobile Mapping System)란 차량 운전 지원용 지도 생성을 위해 고성능 레이저 스캐너 장치인 라이다(LiDAR)를 포함한 다양한 센서를 활용하여, 도로 및 주변 지형 등의 정보를 빠짐없이 취득하는 최첨단 3차원 공간 정보 조사 시스템이다. 이렇게 제작된 정밀 지도는 내년 상반기 제네시스 G90 등에 적용되는 LV3 자율 주행을 구현하기 위한 핵심 기술로 자리매김한다.

당신이 가지고 있는 정밀 지도에는 한 도로에서 찍은 물체 정보들이 담겨 있으며, 그 정보를 아래와 같이 표현할 수 있다.

• 지도는 N개의 구간으로 나뉘어 있고, 각 구간마다 물체가 정확히 하나씩 있다.
•  Ai는 i번째 구간에 있는 물체가 지면으로부터 떨어져 있는 높이이다.

당신은 이 정보를 활용하여, 아래의 제약 조건에 맞게 배너를 걸고자 한다.

• 배너는 지도에 표현된 N개의 구간 중 연속된 M개의 구간에 걸쳐서 걸어야 한다.
• 배너가 있는 연속된 M개의 구간에서 ⌈9M/10⌉개 이상의 Ai의 값이 하나의 값으로 같아야 한다. (⌈x⌉는 보다 크거나 같은 가장 작은 정수를 의미한다.)

이때, 도로에 배너를 걸 수 있는지 확인하는 프로그램을 작성하라.

입력

---

첫째 줄에 정수 N과 M이 공백을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 2×10⁵)

둘째 줄에 정수 A₁, A₂, ⋯, A_N이 공백을 사이에 두고 주어진다. (1 ≤ A_i ≤ 10⁶)

 

출력

---

배너를 걸 수 있다면 YES를, 그렇지 않다면 NO를 출력한다.

 

문제 풀이

---

슬라이딩 윈도우 문제.

 

map을 사용해서 <높이, 길이 m짜리 구간에 존재하는 개수>를 <key,value> 값으로 저장하는 방식을 사용하였다.

처음에는 1부터 m까지 m짜리 구간의 데이터를 map에 넣어준다. 이 과정에서 map의 value가 기준보다 크거나 같다면 배너를 걸 수 있는지를 저장하는 boolean 타입 변수를 true로 변경해준다. 그 이후 m+1부터 n까지 반복하며 슬라이딩 윈도우의 맨 앞에 존재하는 원소의 데이터는 빼주고, 새로 윈도우에 들어가는 원소의 데이터는 더해준다. 즉, 물체 정보를 저장하는 배열이 arr라고 한다면, map에서 arr[i-M]의 값을 1 빼주고 arr[i]의 값을 1 증가시켜주면 된다. 마찬가지로 이 과정에서 map의 value가 기준보다 크거나 같다면 변수를 true로 변경해주고 빠져나오면 된다.

 

아래는 코드.

#include <iostream>
#include <map>
#include <cmath>
using namespace std;

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

	int N, M;
	cin >> N >> M;
	map<int, int> m;
	map<int, int>::iterator it;
	int* arr = new int[N+1];
	int standard = 0;
	if ((9 * M) % 10 == 0)
	{
		standard = 9 * M / 10;
	}
	else
	{
		standard = 9 * M / 10;
		standard++;
	}
	bool canMake = false;
	for (int i = 1; i <= N; i++)
	{
		cin >> arr[i];
	}
	for (int i = 1; i <= M; i++)
	{
		it = m.find(arr[i]);
		if (it == m.end())
		{
			m.insert({ arr[i], 1 });
			if (1 >= standard)
			{
				canMake = true;
				break;
			}
		}
		else
		{
			it->second++;
			if (it->second >= standard)
			{
				canMake = true;
				break;
			}
		}
	}
	if (canMake == false)
	{
		for (int i = M+1; i <= N; i++)
		{
			if (arr[i] == arr[i - M])
			{
				continue;
			}
			else
			{
				it = m.find(arr[i - M]);
				it->second--;

				it = m.find(arr[i]);
				if (it == m.end())
				{
					m.insert({ arr[i], 1 });
					if (1 >= standard)
					{
						canMake = true;
						break;
					}
				}
				else
				{
					it->second++;
					if (it->second >= standard)
					{
						canMake = true;
						break;
					}
				}
			}
		}
	}
	if (canMake == true)
	{
		cout << "YES" << "\n";
	}
	else
	{
		cout << "NO" << "\n";
	}
	return 0;
}