[백준 | JAVA] 27527 - 배너 걸기 (슬라이딩 윈도우)

https://www.acmicpc.net/problem/27527
keyword : 슬라이딩 윈도우

문제

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

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

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

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

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

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

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

입력

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

둘째 줄에 정수 $A_1, A_2, \cdots, A_N$이 공백을 사이에 두고 주어진다. ($1 \le A_i \le 10^6$)

출력

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

 

---

 

풀이

슬라이딩 윈도우를 이용하여 해결하는 문제다.

A의 범위 때문에 그냥 배열이 아니라 Map을 사용해야겠다고 판단하고 HashMap을 사용했는데, 그냥 배열을 사용하는 것이 시간적으로도, 공간적으로도 이득이라는 것을 제출 후 다른 분들의 코드를 보고 알았다.

• $1 \le A_i \le 10^6$

입력으로 들어올 수 있는 A의 최댓값은 $10^6$으로 100만이다. 그래서 그냥 int형 배열을 사용하면 효율성 체크에서 실패할 거라고 판단했는데, 이것이 잘못된 판단이었다.

1. 일단 문제의 메모리 제한이 1024 MB (추가 메모리 없음)으로 굉장히 널널하다.
2. Map을 사용한다고 하여, 공간적으로 이득을 보는 것도 아니다.

1번의 경우에는 그냥 내가 제대로 조건을 읽지 않고 넘어간 탓에 발생한 이슈였다. 이것을 봤으면 그냥 배열을 사용했을 것이다. (그래도 이 실수 덕분에 약간의 깨달음을 얻었으니 이득인가?)

2번의 경우에는 의아할 수 있다.

그렇다면 이걸 생각해보자. A의 배열이 주어질 때, 예제 입력처럼 같은 수가 연속적으로 주어진다면 상관없다.

5 4 4 4 4 4 4 5 4 4 4 4

하지만 입력으로 아래와 같이 주어진다면 어떨까?

1 2 3 4 5 6 7 ... 50000 50001 50002

Map을 사용하여 값을 체크했다면, 매 반복마다 Map에 요소를 삽입하는 연산이 진행될 것이다. 즉, 여기서 시간적으로 손해를 본다. 또 당연하게도 Map은 배열보다 메모리 소모가 더 크다.

그렇기에 이 문제에서는 Map을 사용하는 것이 손해라는 결론이 나온다.

실제로 백준에 코드를 제출했을 떄도 배열을 이용해 구현한 것이 메모리 사용량도 더 적고, 시간도 빠른 것을 확인할 수 있다. 위(90519419)가 HashMap, 아래(90519276)가 배열을 이용해 구현한 코드이다.

 

코드

HashMap

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(stk.nextToken());
        int M = Integer.parseInt(stk.nextToken());

        int[] map = new int[N];

        stk = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            map[i] = Integer.parseInt(stk.nextToken());
        }

        int check = (9 * M + 9) / 10;

        boolean resultFlag = false;
        Map<Integer, Integer> window = new HashMap<>();

      // HashMap 사용
        for (int i = 0; i < N; i++) {
            window.put(map[i], 1 + window.getOrDefault(map[i], 0));

            if(i >= M) window.put(map[i - M], window.get(map[i - M]) - 1);

            if(window.get(map[i]) >= check) {
                resultFlag = true;
                break;
            }
        }

        System.out.println(resultFlag ? "YES" : "NO");
    }
}

 

배열

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.HashMap;  
import java.util.Map;  
import java.util.StringTokenizer;  

public class Main {  
    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        StringTokenizer stk = new StringTokenizer(br.readLine());  

        int N = Integer.parseInt(stk.nextToken());  
        int M = Integer.parseInt(stk.nextToken());  

        int[] map = new int[N];  

        stk = new StringTokenizer(br.readLine());  
        for (int i = 0; i < N; i++) {  
            map[i] = Integer.parseInt(stk.nextToken());  
        }  

        int check = (9 * M + 9) / 10;  

        boolean resultFlag = false;
        int[] numCnt = new int[1000001];  
        for (int i = 0; i < N; i++) {  
            numCnt[map[i]]++;  

            if(i >= M) numCnt[map[i - M]]--;  

            if(numCnt[map[i]] == check) {  
                resultFlag = true;  
                break;  
            }  
        }  


        System.out.println(resultFlag ? "YES" : "NO");  
    }  
}