010 : Deque + Sliding Window

 

 

 

 

오른쪽으로 쌓고, 왼쪽으로 잘라낸다

 

 

3가지 작업 (인식자 = 넣을거)

- 넣기

- 넣을 때 L을 벗어나는 것 제거(4-3 = 1)

- 넣는것보다 큰것은 미리 제거하고 넣음

 

*접근 : field > pointer(deque.getFirst()); 

 

 

 

 

 

 

*connector를 사용 / 별도 class Node 사용

*for i 의 connector 외에 별도 기수 할당이 필요하면 Node를 사용(특히 비교)

 

 

 

 

 

 

 

 

 

import java.io.*;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {

        // ISC
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int V = Integer.parseInt(st.nextToken());
        int L = Integer.parseInt(st.nextToken());

        // D2F
        st = new StringTokenizer(br.readLine());
        Deque<Node> mydeque = new LinkedList<>();

        // OP + OEC patch
        for (int i = 0; i < V; i++) {

            int now = Integer.parseInt(st.nextToken());

            while (!mydeque.isEmpty() && mydeque.getLast().value > now) {
                mydeque.removeLast();
            }

            mydeque.addLast(new Node(i, now));

            if (mydeque.getFirst().pointer <= i-L) {
                mydeque.removeFirst();
            }

            // OEC
            bw.write(mydeque.getFirst().value + " ");
        }
        bw.flush();
        bw.close();
    }

    static class Node {
        int pointer;
        int value;

        Node(int pointer, int value) {
            this.pointer = pointer;
            this.value = value;
        }

    }
}

 

 

 

 

 

 

 

 

 

 

(사고 경향)

- for는 공간을 한 차원 확장

- 공간 위치값 = index // 공간 상태값 = value

- 함수 사용시 항상 위치 먼저 할당(이 일들이 어디서 일어나는지 : mydeque.removeLast();)

- 하나 하나 만든 뒤 작업하지 말고, 작업하면서 만들수 있나 생각해본다