[BOJ/Silver 1] 백준 27527 배너 걸기(C++)

문제 링크

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

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⌉는 x보다 크거나 같은 가장 작은 정수를 의미한다.)

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

입력

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

둘째 줄에 정수 A1, A2, ⋯, AN이 공백을 사이에 두고 주어진다. (1 ≤ Ai ≤ 10^6)

출력

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

예제 입력 1

12 11
5 4 4 4 4 4 4 5 4 4 4 4

예제 출력 1

YES

구간 [2, 12]에 높이 값 4가 ⌈99 / 10⌉개 이상 있으므로, 여기에 배너를 설치할 수 있다.

예제 입력 2

12 11
3 4 4 4 4 4 4 5 4 4 4 3

예제 출력 2

NO

알고리즘 분류

• 슬라이딩 윈도우

풀이

첫 구간에서 특정 값이 ⌈9M / 10⌉개 이상 존재하는지를 따진다. 존재한다면 바로 YES를 출력한다.

존재하지 않으면 구간을 계속 옮기면서 빠지게 되는 값의 개수를 감소시키고 새로운 값의 개수를 증가시킨다. 이 때 새로운 값의 개수가 ⌈9M / 10⌉개 이상이 된다면 바로 YES를 출력한다.

구간을 끝까지 옮겼는데도 ⌈9M / 10⌉개 이상 존재하는 값이 없다면 NO를 출력한다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>
#define MAX 200001
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, M;
int Count = 0;
int A[MAX];
unordered_map<int, int> UM;
bool Answer;

void input() {
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        cin >> A[i];
    }
}

void settings() {
    if ((9 * M) % 10 == 0) {
        Count = (9 * M) / 10;
    }
    else {
        Count = (9 * M) / 10;
        Count++;
    }
    for (int i = 1; i <= M; i++) {
        int Now = A[i];
        UM[Now]++;
        if (UM[Now] == Count) {
            Answer = true;
            return;
        }
    }
    for (int i = (M + 1); i <= N; i++) {
        int Prev = A[i - M];
        int Next = A[i];
        UM[Prev]--;
        UM[Next]++;
        if (UM[Next] == Count) {
            Answer = true;
            return;
        }
    }
}

void find_Answer() {
    if (Answer) {
        cout << "YES\n";
    }
    else {
        cout << "NO\n";
    }
}

int main() {
    FASTIO
    input();
    settings();
    find_Answer();

    return 0;
}