BOJ) 달려라 홍준 (1306 번)

달려라 홍준

1306번: 달려라 홍준

슬라이딩 윈도를 공부하기 위해 푼 문제였다.

슬라이딩 윈도는 주로 두 개의 네트워크 호스트간의 패킷의 흐름을 제어하기 위한 방법으로 사용된다.

고정된 크기의 윈도우가 전체 범위에서 움직이는 방식이다.

배열로 된 예시를 통해 이해하는게 더 수월했다.

 

http://techieme.in/maximum-element-sliding-window/

위와 같은 배열에서 3의 크기로 전체를 탐색하는 경우 사용한다고 생각하면 편하다.

여러 블로그를 찾아봤는데, 슬라이딩 윈도의 핵심은 이전 값에 대해 중복되는 부분을 재사용한다는 것이었다.

이를 통해, 탐색시간을 비약적으로 줄이고, 공간의 효율성 또한 O(n)으로 만들 수 있다.

 

이 문제에서 여러 시도를 해봤지만, 시간과 공간의 효율성 모두 잡을 수 있는 자료구조가 우선순위 큐라고 생각했다. 우선순위 큐에 최댓값으로 정렬을 하고 동시에 인덱스를 남겨두면 충분히 활용할 수 있다고 생각했다.

 

문제를 보면, 입력받은 m의 위치에서 전,후로 m-1까지 모든 배열을 탐색해야한다.

즉, 2*m -1의 크기를 가진 윈도우를 이용해서 탐색해야한다.

위의 조건에 따라서, 우선 초기 위치의 값들을 우선순위 큐에 입력해주었다.

이 때, 2*m -1 과 n의 상관관계가 주어지지 않아서 out of index 방지를 위해 조건문을 걸어주었다.

 

다음으로는 마지막 배열까지 탐색하면서 먼저 값을 입력해주고, 우선순위 큐에서 값을 빼내서 현재 탐색하는 위치에 해당하는 값인지 파악해주었다.이 때, 기준이 되는 위치를 i-m+1로 주었는데, 처음 홍준이가 달리는 위치가 m에서 시작한다는 조건 때문이다.이미 범위를 지나가버린 값은 우선순위 큐에서 빼주면서 답을 구했다.

 

 

 

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[] roads = new int[n];

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++) {
            roads[i] = Integer.parseInt(st.nextToken());
        }

        br.close();
        solution(n,m,roads);
    }

    private static void solution(int n, int m, int[] roads) {
        StringBuilder sb = new StringBuilder();
        final char SPACE = ' ';
        PriorityQueue<AdsBoard> pq= new PriorityQueue<>();
        int range = 2*m-1;
        for(int i=0; i<range; i++) {
            if(i < n) {
                pq.offer(new AdsBoard(i, roads[i]));
            }
        }
        sb.append(pq.peek().intensity).append(SPACE);

        for(int i=range; i<n; i++) {
            pq.offer(new AdsBoard(i, roads[i]));
            boolean found = false;
            while(!found) {
                AdsBoard board = pq.peek();
                if(isInRange(board.index, i-m+1, m)) { // 번호를 붙이는거는 i-m+1 번째 ( m을 시작으로 증가)
                    found = true;
                    sb.append(board.intensity).append(SPACE);
                } else {
                    pq.poll();
                }
            }
        }

        System.out.println(sb.toString());
    }

    private static boolean isInRange(int intensity, int i, int m) {
        return intensity > i-m && intensity < i+m;
    }

    private static class AdsBoard implements Comparable<AdsBoard>{
        int index, intensity;

        public AdsBoard(int index, int intensity) {
            this.index = index;
            this.intensity = intensity;
        }

        @Override
        public int compareTo(AdsBoard board) {
            if(board.index == this.index) {
                return this.index - board.index;
            } else {
                return board.intensity - this.intensity;
            }
        }
    }
}