Naive Solution

이 문제를 풀기 위한 가장 간단한 풀이는 각 위치에 대해서 슬라이딩 윈도를 직접 대어 보고 최대값과 최소값이 무엇인지 찾는 것입니다. 2중 for문을 통해서 구현하면 되겠죠. O(NK)입니다.

#include<vector>
using namespace std;

void slidingwindow_naive(vector<int> &array, vector<int> &minv, vector<int> &maxv){
    int pos;
    for(pos=0; pos < array.size(); ++pos){
        int minval = maxval = array[pos];
        int i;

        for(i=1;i<K;++i){
            minval = min(minval, array[i]);
            maxval = max(maxval, array[i]);
        }

        minv.push_back(minval);
        maxv.push_back(maxval);
    }
}

하지만 이 풀이는 너무나 느립니다. N의 크기가 1000000까지 될 수 있고 K도 마찬가지이므로 이런 경우에는 아무리 코드를 최적화한다 하더라도 시간내에 답이 나오지 않습니다.

Binary-search Tree

이진 탐색 트리는 이진 트리의 일종으로 각 노드의 왼쪽 자식은 부모 노드가 지닌 값보다 작은 값을 지니고, 오른쪽 자식은 부모보다 큰 값을 갖도록 구성되어 있습니다. 균형잡힌 이진 트리의 경우 데이터의 삽입, 삭제가 O(lg N)만에 가능합니다.

그리고 중요한 특징은, 이진 탐색 트리의 최소값과 최대값 역시 O(lg N)에 구할 수 있다는 것입니다. 이 방법 역시 O(N lg N)에 해결이 가능합니다.

#include<set>
#include<vector>
#include<utility>
using namespace std;

void slidingwindow_bst(vector<int> array, vector<int> &minv, vector<int> &maxv){
    // (value, pos) 쌍으로 저장
    // C++ pair의 기본 less 연산은 앞에 오는 원소를 먼저 비교함 :)
    set<pair<int, int> > bst;
    int i;
    for(i = 0; i < K; ++i)
        bst.insert( make_pair(array[i], i) );

    minv.push_back( bst.begin() -> first );
    maxv.push_back( bst.rbegin() -> first );

    for(i = K; i < array.size(); ++i){
        bst.erase( make_pair( arrray[i - K], i-K );
        bst.insert(make_pair( array[i]     , i   );
        minv.push_back( bst.begin() -> first );
        maxv.push_back( bst.rbegin() -> first );
    }
}

Indexed Tree 인덱스 트리라는 자료구조는 완전 이진 트리의 일종인데, 알고리즘 경시에 참여하는 사람들 사이에서 통용되는 이름입니다. 구간 트리라고도 불리는데 일반적인 구간 트리와는 약간 다릅니다. 일단 이 트리는 완전 이진 트리이므로 N보다 크거나 같은 가장 작은 2의 지수를 M이라 할 때, 2*M개의 저장공간을 필요로 합니다.

각 노드는 자신이 가리키는 구간을 ‘대표하는’ 값을 지니게 됩니다. 예를 들어 이 문제의 경우 트리의 루트 노드는 Min( Array[0..M-1] ) 또는 대응되는 Max의 값을 가지게 되겠죠. 루트의 왼쪽 노드는 0 ~ M/2-1까지의 구간을 대표하고, 루트의 오른쪽 노드는 M/2 ~ M-1까지를 대표하고.. 이런 식으로 깊이가 한단계 깊어질 때마다 노드가 대표하는 구간의 크기가 절반씩 줄어듭니다. 깊이가 log M이 되면 각각 길이 1의 구간을 대표하고 있게 되죠. (그 위치에 해당하는 Array의 값을 지닌다는 뜻)

트리의 갱신은 일단 가장 끝부분의 값을 바꾸고, 부모 노드를 하나씩 타고 올라오면서 값을 갱신해 줍니다. 두 자식의 값을 보고 자기자신을 바꾸는 recursive 함수를 작성하면 되겠죠?

이렇게 하면 임의의 구간에 대한 값을 구하는 건 lg M 개의 노드만 선택하면 어떤 구간이라도 커버가 가능하기 때문에… O(lg M) = O(lg N)입니다. M < 2*N이니까요.

#include<vector>
#include<algorithm>
#include<functional>
#include<iostream>
using namespace std;

class IndexedTree{
private:
    vector<int> minTree;
    vector<int> maxTree;

    int treeBegin;  
    void initTree(){
        int here;
        for(here = treeBegin - 1; here >= 1; --here){
            const int leftChild = here * 2;
            const int rightChild = leftChild + 1;

            minTree[here] = minTree[leftChild] < minTree[rightChild]? minTree[leftChild] : minTree[rightChild];
            maxTree[here] = maxTree[leftChild] > maxTree[rightChild]? maxTree[leftChild] : maxTree[rightChild];
        }       
    }
public:
    IndexedTree(vector<int> data){
        for(treeBegin = 1; treeBegin < data.size(); treeBegin <<=1);

        minTree.resize(treeBegin * 2);
        maxTree.resize(treeBegin * 2);

        copy(data.begin(), data.end(), minTree.begin() + treeBegin);
        copy(data.begin(), data.end(), maxTree.begin() + treeBegin);

        initTree();
    }

    int getMin(int firstIndex, int lastIndex){
        firstIndex += treeBegin;
        lastIndex += treeBegin;

        int result = 0x7fffffff;
        while(firstIndex < lastIndex){
            result = min(result, minTree[firstIndex]);
            result = min(result, maxTree[lastIndex]);

            firstIndex = (firstIndex + 1) >> 1;
            lastIndex = (lastIndex - 1) >> 1;
        }
        if(firstIndex == lastIndex)
            return min(result, minTree[firstIndex]);
        return result;
    }

    int getMax(int firstIndex, int lastIndex){
        firstIndex += treeBegin;
        lastIndex += treeBegin;

        int result = -2147483648;
        while(firstIndex < lastIndex){
            result = max(result, maxTree[firstIndex]);
            result = max(result, maxTree[lastIndex]);

            firstIndex = (firstIndex + 1) >> 1;
            lastIndex = (lastIndex - 1) >> 1;
        }
        if(firstIndex == lastIndex)
            return max(result, maxTree[firstIndex]);
        return result;
    }
};

int main(){
    int n, k, i;
    cin >> n >> k;

    vector<int> data(n);
    for(i = 0; i < n; ++i){
        cin >> data[i];
    }

    vector<int> mins;
    vector<int> maxs;
    IndexedTree it(data);

    mins.reserve(n-k+1);
    mins.reserve(n-k+1);
    for(i = k-1; i < n; ++i){
        mins.push_back( it.getMin(i-k+1, i) );
        maxs.push_back( it.getMax(i-k+1, i) );
    }

    for(i = 0; i < mins.size(); ++i){
        cout << mins[i] << " ";
    }
    cout << "\n";
    for(i = 0; i < maxs.size(); ++i){
        cout << maxs[i] << " ";
    }
    return 0;
}

Optimal Solution

일단 배열을 2*K-1개씩 쪼갭니다. K=4이라면 배열을 7개 단위로 자르게 되겠네요. 다음을 봅시다.

A[0] A[1] A[2] A[3] A[4] A[5] A[6]

이때 중앙에서부터 계산을 시작하면 다음과 같은 배열은 O(K)만에 계산이 가능하겠죠?

Min[0..3] Min[1..3] Min[2..3] A[3] Min[3..4] Min[3..5] Min[3..6]

그런데 이걸 잘 보시면요. 이 배열만으로 슬라이딩 윈도우 내에서 최소값이 무엇인지 다 알 수 있어요.

Min[0..3]은 배열 안에 있고요. Min[1..4] = Min[1..3]과 Min[3..4] 중 작은 값이죠. Min[2..5]는 Min[2..3]과 Min[3..5]중에 작은 값이죠…

어헣 간단하죠? 2*K-1개씩 배열을 나누면 대충 O(N/K)개의 부분배열이 나오죠? 각각의 부분배열에서 최대값과 최소값을 구하는 것은 O(K)만에 되니까 O(N/K) * O(K) = O(N) 이 되는 것입니다.

#include<cstdio>
#include<vector>
using namespace std;

int N,K;
inline int min(int a,int b){return a>b?b:a;}
inline int max(int a,int b){return a>b?a:b;}

const int maxn=1000000;
int data[2*maxn],deque_min[2*maxn],deque_max[2*maxn],M[maxn];

int main(){
    //var;
    int pivot,i,j,c;

    //code
    scanf("%d %d",&N,&K);   

    for(i=0;i<N;i++)
        scanf("%d",&data[i]);

    for(c=0,pivot=K-1;pivot<N;pivot+=K){
        deque_max[K-1]=deque_min[K-1]=data[pivot];

        for(i=1;i<K;i++){
            deque_min[K-i-1]=min(deque_min[K-i],data[pivot-i]);
            deque_max[K-i-1]=max(deque_max[K-i],data[pivot-i]);

            if(pivot+i-1 >= N-1) {
                deque_max[K+i-1]=deque_min[K+i-1]=0x7fffffff;
            }
            else {
                deque_min[K+i-1]=min(deque_min[K+i-2],data[pivot+i]);
                deque_max[K+i-1]=max(deque_max[K+i-2],data[pivot+i]);
            }
        }
        for(i=0,j=K-1;i<K;++i,++j){
            if(++c > N-K+1) break;  
            M[c-1]=max(deque_max[i],deque_max[j]);
            printf("%d ",min(deque_min[i],deque_min[j]));
        }
    }
    printf("\n");
    for(i=0;i<N-K+1;++i)
        printf("%d ",M[i]);

    return 0;
}

윈도우는 항상 정렬된 상태로 유지됩니다. 윈도우가 한칸 움직이면, 윈도우에서 왼쪽으로 벗어난 값은 윈도에서 지워비립니다. 오른쪽에 새로 추가된 값은 윈도우에 적절한 위치를 찾아서 삽입합니다. 정렬되어 있으므로 항상 윈도우의 젤 좌측값이 최소값, 젤 우측값이 최대값입니다. bisect.insort()는 파이썬 기본라이브러리에 있구요, 정렬된 리스트에 정렬 상태를 유지하면서 원하는 값을 삽입하는 매우 빠른 메소드입니다.

import bisect
a, w = map(int, raw_input().split())
array = list(map(int, raw_input().split()))
window = array[:w]
window.sort()
mins=[window[0]]
maxs=[window[-1]]
for i in range(1,a-w+1):
    window.remove(array[i-1])
    n = array[i+w-1]
    bisect.insort(window,n)
    mins.append(window[0])
    maxs.append(window[-1])
for i in mins:print i,
print
for i in maxs:print i,

Euclid Problem에서 길가의풀님께서 사용하신것처럼 저도 재귀를 사용해봤습니다. 먼저 파일을 읽어온 다음, 비교할 숫자들의 수(num_size), 윈도우 크기(win_size), 숫자들(numbers)를 읽어옵니다. 그런다음 각 윈도우별로 비교하기위해 find_extrema 함수를 호출하는데 이때 윈도우를 옮기는 것보다 비교가 끝난 숫자들을 버리는게 나을것같아서 number.pop(0)으로 숫자들을 버린뒤 다시 find_extrema 함수를 반복적으로 호출하는 방식입니다. 이때 다른 loop를 넣지않기 위해서 버리면서 계속 비교해나가다가 numbers가 비어버리면 에러를 출력하면서 결과를 리턴하게 해봤습니다. 그리고 최종적인 result는 크기가 8인 리스트를 2개 가지고있는데 맨 뒤의 2개는 numbers의 사이즈가 윈도우의 크기보다 작을때 비교한것이기 때문에 버리고 값을 출력했습니다.

import os
import sys

#
# Find Maximum and Minimum in each window
#
def find_extrema(win_size, numbers, result=[ [], [] ]):

    try :
        result[0].append(str(min(numbers[:win_size])))
        result[1].append(str(max(numbers[:win_size])))
        numbers.pop(0)
    except ValueError : return result

    return find_extrema(win_size, numbers, result)

#
# Main Part
#

path = os.path.dirname(os.path.abspath(__file__))

try : f = open(path + "/input.txt", 'r')
except IOError : print("There isn't the input file 'input.txt'"); sys.exit()

line_1 = f.readline()
line_2 = f.readline()

num_size, win_size = map(int, line_1.split())
numbers = list(map(int, line_2.split()))

if num_size > 10E6 or len(numbers) != num_size:
    print("Wrong Input! Check 'input.txt'.")
    sys.exit()
else :
    result = find_extrema(win_size,numbers)

print(" ".join(result[0][:-2]))
print(" ".join(result[1][:-2]))

파이썬입니다.

1,000,000 개이고 k가 1,000 일 때 제 PC에서 20초 가량 걸립니다.
K가 10,000 이상 넘어가면 답이 안나오네요, 너무 느려서..

위에 Kim Jaeju 님이 알려주신 알고리즘을 사용해 봐야 할 것 같습니다.

def slide(src, k):
    window = map(int, src.split())
    last_index = len(window)-k
    r1, r2 = [], []
    for i in range(last_index+1):
        current_window = window[i:i+k]
        current_window.sort()
        r1.append(current_window[0])
        r2.append(current_window[-1])
    return r1, r2

print slide("1 3 -1 -3 5 3 6 7", 3)

개선 1

bisect 모듈을 이용하여 윈도우 이동 시 매번 소트를 하지 않고 최초 한번만 소트한 후 값을 배열에 입력할 때 자동으로 정렬되도록 수정 해 보았습니다. (Kim Jaeju 님의 Binary-search Tree 를 참조하였습니다.)

import bisect

def slide(src, k):
    window = map(int, src.split())
    last_index = len(window)-k
    r1, r2 = [], []

    current_window = window[0:k]
    current_window.sort()
    r1.append(current_window[0])
    r2.append(current_window[-1])

    for i in range(last_index):
        current_window.remove(window[i])
        bisect.insort(current_window, window[k+i])
        r1.append(current_window[0])
        r2.append(current_window[-1])

    return r1,r2

수행 결과:

n:1,000,000, k:1,000 --> 2초
n:1,000,000, k:10,000 --> 7초
n:1,000,000, k:100,000 --> 50초

개선은 되었지만 만족스럽진 않네요.. (이 알고리즘은 k가 커질수록 불리해 보이네요.)

import java.util.ArrayList;
import java.util.Scanner;

public class SlidingWindow {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String temp = sc.nextLine();
        String[] Winpos = temp.split(" ");
        int size = Integer.valueOf(Winpos[1]);
        temp = sc.nextLine();
        Winpos = temp.split(" ");
        ArrayList<Integer> minA = new ArrayList<>();
        ArrayList<Integer> maxA = new ArrayList<>();
        for (int k = 0; k < Winpos.length - size + 1; k++) {
            int min = Integer.valueOf(Winpos[k]);
            int max = Integer.valueOf(Winpos[k]);
            for (int i = k + 1; i < size + k; i++) {
                min = min > Integer.valueOf(Winpos[i]) ? Integer.valueOf(Winpos[i]) : min;
                max = max < Integer.valueOf(Winpos[i]) ? Integer.valueOf(Winpos[i]) : max;
            }
            minA.add(min);
            maxA.add(max);
        }
        System.out.println(minA.toString());
        System.out.println(maxA.toString());
    }
}

node.js (Javascript)로 짰습니다. K가 증가할수록 속도가 영 안나오는군요. 배열을 다루는 방법에 따라, 기본 제공되는 수학함수를 쓰느냐 안쓰느냐에 따라서 퍼포먼스 편차가 엄청 심하네요. Kim Jaeju님 솔루션 보고 공부좀 해야 할 것 같습니다.

var fs = require('fs');
var util = require('util');

console.log("[memory] after node.js module load: ");
console.log(util.inspect(process.memoryUsage()));
var timer = process.hrtime();

var data = fs.readFileSync('data.txt', {encoding: 'utf8'}).split("\n");
var dataHeader = data[0].split(" ");
var WINDOW_SCOPE_LENGTH = dataHeader[1];
var WINDOW_ITEMS = data[1].split(" ").map(function (x) { return +x ; });
data = null;
dataHeader = null;

console.log("[memory] after data load: ");
console.log(util.inspect(process.memoryUsage()));
console.log(process.hrtime(timer));


Array.prototype.min = function () {
    return this.reduce(function (p, v) {
        return ( p < v ? p : v );
    });
};
Array.prototype.max = function () {
    return this.reduce(function (p, v) {
        return ( p > v ? p : v );
    });
};

var minValueItems = [];
var maxValueItems = [];
for(var i = 0 ; i < WINDOW_ITEMS.length - WINDOW_SCOPE_LENGTH + 1 ; i++) {
    var scope = [];
    for(var j = 0 ; j < WINDOW_SCOPE_LENGTH; j++) {
        scope.push(WINDOW_ITEMS[i+j]);
    }

    minValueItems[i] = scope.min();
    maxValueItems[i] = scope.max();
}

fs.writeFileSync('result.txt', minValueItems.join(" ") + "\n" + maxValueItems.join(" "));


console.log("[memory] after program execution: ");
console.log(util.inspect(process.memoryUsage()));
console.log(process.hrtime(timer));

n=1,000,000 ,k=1,000만 되도 답이 안나오네요...

#sliding_window.py
import random
import time

start_time=0
end_time=0
def sliding_window():
    column_length = int(raw_input("column's length: "))
    window_length = int(raw_input("sliding window's length: "))
    start_time=time.time()
    row=[]
    for num in range(column_length):
        row.append(random.randint(-9, 9))
    window=[]
    max_number=[]
    min_number=[]
    for num in range(len(row)):
        for leng in range(window_length):
            if num+window_length-1 == len(row):
                end_time=time.time()
                print 'time limit: ',end_time-start_time
                return column_length, window_length, row, max_number, min_number
            window.append(row[num+leng])
        max_number.append(max(window))
        min_number.append(min(window))
        window=[]

column_length, window_length, row, max_number, min_number = sliding_window()

print """
sample input:
%s %s
%s"""%(column_length, window_length, str(row)[1:-1])

print """
sample output:
%s
%s"""%(str(min_number)[1:-1], str(max_number)[1:-1])

column's length: 8
sliding window's length: 3
time limit:  0.0

sample input:
8 3
1, 6, 4, 0, 5, -9, 1, 0

sample output:
1, 0, 0, -9, -9, -9
6, 6, 5, 5, 5, 1

JAVA

package Ex03;

import java.util.Scanner;

public class go2 {

    public static void main(String args[]) {

        Scanner sc = new Scanner(System.in);
        System.out.println("배열의 크기와 슬라이딩윈도우의 크기 입력");
        int[] array = new int[sc.nextInt()];
        int[] slidingWindow = new int[sc.nextInt()];
        System.out.println("배열의 값 입력 (" + array.length + "개)");
        for (int i = 0; i < array.length; i++)
            array[i] = sc.nextInt();
        startSliding(array, slidingWindow);

    }

    public static void startSliding(int[] array, int[] slidingWindow) {

        int[] max = new int[array.length - slidingWindow.length + 1];
        int[] min = new int[array.length - slidingWindow.length + 1];
        int maxValue = 0, minValue = 0;

        for (int i = 0; i < array.length - slidingWindow.length + 1; i++) {
            for (int j = 0; j < slidingWindow.length; j++)
                slidingWindow[j] = array[j + i * 1];
            maxValue = slidingWindow[0];
            minValue = slidingWindow[0];
            for (int k = 0; k < slidingWindow.length - 1; k++) {
                if (slidingWindow[k + 1] > maxValue)
                    maxValue = slidingWindow[k + 1];
                if (slidingWindow[k + 1] < minValue)
                    minValue = slidingWindow[k + 1];
            }
            max[i] = maxValue;
            min[i] = minValue;
        }

        System.out.println(" array.length : " + array.length +
                  "    slingWindow.length : " + slidingWindow.length);
        System.out.print(" value : ");
        for (int i = 0; i < array.length; i++)
            System.out.print(array[i] + " ");
        System.out.print("\n MAX : ");
        for (int i = 0; i < max.length; i++)
            System.out.print(max[i] + " ");
        System.out.print("\n MIN : ");
        for (int i = 0; i < min.length; i++)
            System.out.print(min[i] + " ");
        System.out.println();

    }

}

배열의 크기와 슬라이딩윈도우의 크기 입력

10 3

배열의 값 입력 (10개)

6 5 2 3 1 82 5 7 3 91

array.length : 10 slingWindow.length : 3

value : 6 5 2 3 1 82 5 7 3 91

MAX : 6 5 3 82 82 82 7 91

MIN : 2 2 1 1 1 5 3 3

def core03(k):
    result=[]
    temp=a[:k]
    NumMax=0
    NumMin=0
    for i in range(len(a)-k+1):

        if i==0:
            result.append([min(temp),max(temp)])
        else:
            PrevMin , PrevMax = result[-1][0] , result[-1][1]
            OutNumber=temp.pop(0)
            InNumber=a[k+i-1]
            temp.append(InNumber)
            if OutNumber==PrevMin:
                CurMin=min(temp)
                NumMin+=1
            elif InNumber<PrevMin:
                CurMin=InNumber
            else:
                CurMin=PrevMin

            if OutNumber==PrevMax:
                CurMax=max(temp)
                NumMax+=1
            elif InNumber>PrevMax:
                CurMax=InNumber
            else:
                CurMax=PrevMax
            result.append([CurMin,CurMax])
    print(NumMax,NumMin)
    return result

import cProfile



n=10**6

k=10**5

a= [1, 3, -1, -3, 5, 3, 6, 7]
cProfile.run('print(core03(3))')
#1 1
#[[-1, 3], [-3, 3], [-3, 5], [-3, 5], [3, 6], [3, 7]]
         #27 function calls in 0.000 seconds

a=[int(random.randint(0,10))//1 for i in range(n)]
#81864 81691
#[[0, 10], [0, 10], [0, 10], [0, 10], [0, 10], [0, 10], [0, 10], [0, 10], [0, 10], [0, 10]]
         #2863565 function calls in 477.668 seconds
#10개 정도의 숫자가 반복하는 경우에는 취약한 모습입니다. 뭐 그럴수 밖에 없지만.. 

a=[int(random.gauss(0,10))//1 for i in range(n)]
#13 12
#[[-46, 48], [-46, 48], [-46, 48], [-46, 48], [-46, 48], [-46, 48], [-46, 48], [-46, 48], [-46, 48], [-46, 48]]
         #2700035 function calls in 21.682 seconds
cProfile.run('print(core03(k)[:10])')

python3.4 로 작성.

들어오는 수와 나가는 수를 이전 최대값 최소값과의 비교후 나가는 수가 최대값 또는 최소값과 같다면 최대치 최소치 찾는 함수를 돌리고

들어오는 수가 이전 최대값 보다 크거나 최소값보다 작으면 이번 최대값 또는 최소값을 변환.

그렇지 않으면 유지하는 방식으로 작성하였습니다.

따라서 수열의 성향을 좀 타는 방식이 되어버렸네요. 같은 값 randint 와 같은 랜덤 함수로 돌리면 최대치 최소치 함수를 무작정 쓰게 되버리는 단점이 있습니다.

C#으로 작성했습니다. time complexity: O(n), space complexity: O(n) 입니다.

using System.Collections.Generic;

        public int[] GetMaxSlidingWindow(List<int> inputs, int w)
        {
            var max_left = new int[inputs.Count];
            var max_right = new int[inputs.Count];
            max_left[0] = inputs[0];
            max_right[inputs.Count - 1] = inputs[inputs.Count - 1];
            for (int i = 1; i < inputs.Count(); i++)
            {
                max_left[i] = (i%w == 0) ? inputs[i] : Math.Max(max_left[i - 1], inputs[i]);
                var j = inputs.Count - i - 1;
                max_right[j] = (j%w == 0) ? inputs[j] : Math.Max(max_right[j + 1], inputs[j]);
            }
            var outputs = new int[inputs.Count - w + 1];
            for (int i = 0, j = 0; i + w <= inputs.Count; i++)
                outputs[j++] = Math.Max(max_right[i], max_left[i + w - 1]);
            return outputs;
        }

        public int[] GetMinSlidingWindow(List<int> inputs, int w)
        {
            var min_left = new int[inputs.Count];
            var min_right = new int[inputs.Count];
            min_left[0] = inputs[0];
            min_right[inputs.Count - 1] = inputs[inputs.Count - 1];
            for (int i = 1; i < inputs.Count(); i++)
            {
                min_left[i] = (i % w == 0) ? inputs[i] : Math.Min(min_left[i - 1], inputs[i]);
                var j = inputs.Count - i - 1;
                min_right[j] = (j % w == 0) ? inputs[j] : Math.Min(min_right[j + 1], inputs[j]);
            }
            var outputs = new int[inputs.Count - w + 1];
            for (int i = 0, j = 0; i + w <= inputs.Count; i++)
                outputs[j++] = Math.Min(min_right[i], min_left[i + w - 1]);
            return outputs;
        }

Ruby

DP로 다시 구현했습니다. bsearch를 이용한 방법은 k값에 처리시간이 비례해서 k가 10만정도만 되어도 굉장히 느려지더군요. DP로 구현한 결과 k가 10만을 넘어가도 2.8 ~ 3.4초 사이에서 처리됩니다(화면 입출력 시간 제외). 알고리즘은 앞뒤로 순회하면서 min/max를 구한 뒤, 이를 이용해서 윈도우의 최소, 최대값을 구하는 방법입니다. 다음에 lazy, 비동기, 컴파일러 언어를 사용해서 다시 풀어보고 싶네요..

l_min = ->s { s.reduce([]) {|a,e| a << [a[-1]||e, e].min } }
r_min = ->s { s.reverse_each.reduce([]) {|a,e| a.unshift([a[0]||e, e].min) } }
l_max = ->s { s.reduce([]) {|a,e| a << [a[-1]||e, e].max } }
r_max = ->s { s.reverse_each.reduce([]) {|a,e| a.unshift([a[0]||e, e].max) } }

s_window = lambda do
  n, k, *arr = 2.times.flat_map { gets.split.map(&:to_i) } # for stdin case
  sl, sr, bl, br, mins, maxs = [[],[],[],[],[],[]]
  arr.each_slice(k) {|s| sl+=l_min[s]; sr+=r_min[s]; bl+=l_max[s]; br+=r_max[s] }
  (0..n-k).each {|i| mins << [sr[i],sl[i+k-1]].min; maxs << [br[i],bl[i+k-1]].max }
  puts mins*' ', maxs*' '
end

Test

$stdin = StringIO.new("8 3\n1 3 -1 -3 5 3 6 7\n")
expect{ s_window[] }.to output("-1 -3 -3 -3 3 3\n" + "3 3 5 5 6 7\n").to_stdout

# performance
arr = (0...1_000_000).map {|i| rand(1_000_000) }
Benchmark.bm(25) do |x|
  x.report("case 1. n=10**6, k=10**4") { s_window[10*6, 10*4, arr] }
  x.report("case 2. n=10**6, k=10**5") { s_window[10*6, 10*5, arr] }
  x.report("case 3. n=10**6, k=5*10**5") { s_window[10*6, 5*10*5, arr] }
end
                                user     system      total        real
case 1. n=10**6, k=10**4    3.240000   0.040000   3.280000 (  3.280056)
case 2. n=10**6, k=10**5    3.220000   0.040000   3.260000 (  3.265054)
case 3. n=10**6, k=5*10**5  2.990000   0.040000   3.030000 (  3.040523)

python 3입니다.

lis = [1,3,-1,-3,5,3,6,7]
ln=len(lis)
wn = 3

for idx in range(0,ln-wn):
    sub_lis = lis[idx:idx+wn+1]
    print(max(sub_lis),end=' ')
    print(min(sub_lis))

완전탐색. O(NK) 문제를 그대로 코드로 옮겼네유

파이썬3.4입니다.

def f(li, k, rt = []):
    mn = min(li[:3])
    mx = max(li[:3])
    if len(li) >= k:
        rt.extend([mn, mx])
        f(li[1:], k, rt)
        retrun rt

li = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
rt = f(li, k)
print(rt[::2])
print(rt[1::2])

아... 영혼도 알고리즘도 없는 결과물이네요. 윗분들이 말씀하시는것들을 생각하기에는, 제가 부족하고... 일단 결과물이라도 나와야겠다는 생각에 만들었습니다.
일단 n이 10^4만 되도 런타임에러가 나옵니다. maximum recursion depth exceeded in comparison
ㅜㅜ

#파이썬 3.4.2
#n,w가 너무 크면 느려질 수 있습니다
n,w = map(int,input().split())
nums = list(map(int,input().split()))
sM = [str(max(nums[x:x+w])) for x in range(n-w+1)]
sm = [str(min(nums[x:x+w])) for x in range(n-w+1)]
print('%s\n%s' % (' '.join(sm),' '.join(sM)))

그냥 무식하게 풀었습니다. 10만개 짜리 랜덤 배열을 이용했을 때에도 대략 200~300ms 내에서 처리되네요.

from random import randrange

l, k = [int(x) for x in input().split()[:2]]
# xs = [int(x) for x in input().split()[:l]]
xs = [randrange(-100, 100) for _ in range(l)]

def minmax(xs):
    return min(xs), max(xs)

def do(xs):
    mins, maxs = [], []
    for i in range(l-k+1):
        x, y = minmax(xs[i:i+k])
        mins.append(x)
        maxs.append(y)
    print(" ".join(str(x) for x in mins))
    print(" ".join(str(x) for x in maxs))

%time do(xs)

Python 3.4.4

data_len, window = map(int, input().split())
data = input().split()

output = [[],[]]

for i in range(-1, data_len - window):
    output[0].append(min(data[:window]))
    output[1].append(max(data[:window]))
    data.append(data.pop(0))

[print(" ".join(x)) for x in output]

from multiprocessing import Pool
from random import randint
from time import time
from bisect import insort
from os import cpu_count
CORES = cpu_count()

def gensrc(i):
    with Pool() as p:
        result = p.starmap(randint, ((-10, 10) for x in range(i)))
    return result
def f(x, y, startpoint, endpoint):
    result = [];temp = sorted(x[startpoint:startpoint+y])
    result.append((temp[0], temp[-1]))
    for i in range(startpoint + 1, endpoint - y):
        temp.remove(x[i-1])
        insort(temp, x[i+y-1])
        result.append((temp[0], temp[-1]))
    return result

while __name__ == '__main__':
    temp = list(map(int, input().split()))
#    target = list(map(int, input().split()))
    target = gensrc(temp[0])
    k = time()
    with Pool() as p:
        res = p.starmap(f, ((target, temp[1], int(x*temp[0]/CORES), int((x+1)*temp[0]/CORES)) for x in range(CORES)))
    print(time()-k)

1000000 100000 48.06775736808777초 나오네요. i7 6700hq 95퍼센트 로드. 2.5기가헤르츠 기준입니다. 샘플 생성시간은 제외하였습니다.

파이썬 3.5.1 64

c++로 풀어봤는데 어렵네요....일단 결과물은 나오는데 시간은 어떨지 모르겠네요 10^5 까지는 잘 되는거 같습니다...?

#include <iostream>
#include <time.h>
#include <stdlib.h>
#define Maxsize 1000000
using namespace std;

void Sliding_window(int n,int k);
void Move_window(int*w_arr,int *arr,int k,int n);
void Binary_Search_Tree(int*w_arr,int k,int L);
void Get_Max_Min(int*M,int*Max_arr,int*Min_arr,int L,int k);
void Print_array(int*arr,int k);
int ARR_LENGTH=0;
int Max_arr[Maxsize];
int Min_arr[Maxsize];
int main()
{
    int n,k;
    cin>>n>>k;
    Sliding_window(n,k);
    Print_array(Min_arr,n-k+1);
    Print_array(Max_arr,n-k+1);
    return 0;
}
void Sliding_window(int n,int k)
{
    int*arr=new int[n];
    int*w_arr=new int[k];
    srand((unsigned int)time(0));
    for(int i=0;i<n;i++)
    {

        arr[i]=rand()%9+1;
    }
    Move_window(w_arr,arr,k,n);
}
void Move_window(int*w_arr,int*arr,int k,int n)
{
    int c=0,L=0;
    for(int i=k-1;i<n;i++)
    {
        c=0;
        for(int j=i-k+1;j<=i;j++)
        {
            w_arr[c]=arr[j];
            c++;
        }

        Binary_Search_Tree(w_arr,k,L);
        L++;
    }


}
void Binary_Search_Tree(int*w_arr,int k,int L)
{
    int root[1000]={0,};
    int now=0,c=1;
    root[0]=w_arr[now];
    while(c<k){
        now=0;
        while(1){

            if(w_arr[c]<root[now]){
                now=(now*2)+1;
            }
            else if(w_arr[c]>root[now]){
                now=(now*2)+2;
            }
            else if(w_arr[c]==root[now])
                break;
            if(root[now]==0)
                break;


        }
        root[now]=w_arr[c];
        c++;
    }
    //Print_array(root,50);
    Get_Max_Min(root,Max_arr,Min_arr,L,k);

}
void Get_Max_Min(int*M,int *Max_arr,int *Min_arr,int L,int k)
{
    int ma=M[0],mi=M[0],c=0;
    for(int i=0;i<100;i++){
        if(M[i]!=0){
            mi=min(mi,M[i]);
            ma=max(ma,M[i]);
            c++;
        }
        if(c==k)
            break;
    }
    Max_arr[L]=ma;
    Min_arr[L]=mi;
}
void Print_array(int*arr,int k)
{
    for(int i=0;i<k;i++){
        cout<<arr[i]<<" ";
    }
    cout<<endl;

}

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <windows.h>
#include <stdio.h>
#include <string>

using namespace std;

void Sliding();
void Printarr(int*, int);
void main() {
    Sliding();
    system("pause");
}

void Sliding() {
    int n, k;
    int min = 9999, max = 0;
    cout << "input (배열크기 n, 윈도우크기 k): ";
    cin >> n >> k;
    int* arr = new int[n];
    int* minarr = new int[n - k + 1];   //최소값 저장할 배열
    int* maxarr = new int[n - k + 1];   //최대값 저장할 배열
    //배열의 요소개수 - 윈도우크기 + 1 은 최소값 혹은 최대값 배열의 크기이다
    cout << "input (배열의 요소): ";
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    for (int i = 0; i < n; i++)
    {
        min = 9999;
        max = 0;
        if (k + i < n + 1) {
            for (int j = i; j < k + i; j++) {
                if (min > arr[j]) {
                    min = arr[j];
                }
                if (max < arr[j]) {
                    max = arr[j];
                }
            }
            minarr[i] = min;
            maxarr[i] = max;
        }
        else {
            break;
        }
    }
    Printarr(minarr, n-k+1);
    Printarr(maxarr, n-k+1);
    delete arr;
    delete minarr;
    delete maxarr;
}
void Printarr(int* arr, int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void main() {
    int arr_size;
    int win_size;
    scanf("%d %d", &arr_size, &win_size);
    int* arr = (int*) malloc (sizeof(int) * arr_size);
    for(int i=0;i<arr_size;i++)
        scanf("%d", &arr[i]);
    int* min = (int*) malloc (sizeof(int) * arr_size-2);
    int* max = (int*) malloc (sizeof(int) * arr_size-2);
    for(int i=0;i<arr_size;i++) {
        min[i] = 100;
        max[i] = 0;
    }

    for(int i=0;i<arr_size-2;i++) {
        int* window = (int*) malloc (sizeof(int) * win_size);
        memmove(window, arr+i, sizeof(int) * win_size);
        for(int j=0;j<win_size;j++) {
            if(window[j] < min[i])
                min[i] = window[j];
            if(window[j] > max[i])
                max[i] = window[j];
        }
    }

    for(int i=0;i<arr_size-2;i++) 
        printf("%d ", min[i]);
    printf("\n");
    for(int i=0;i<arr_size-2;i++)
        printf("%d ", max[i]);
}

import time
start = time.time()
#size, s_size = list(map(int,input(),split(' ')))
size, s_size = 1000000, 1000
max_list,min_list = list(),list()
#_list = list(map(int,input().split(' ')))
_list = [1 for x in range(size)]
for x in range(size-s_size+1):
    max_list.append(max(_list[x:x+s_size]))
    min_list.append(min(_list[x:x+s_size]))
#print(min_list,max_list,sep='\n')
print(time.time()-start)

#### 2017.02.01 D-386 ####

import java.util.Arrays;
import java.util.Scanner;

public class SlidingWindow {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int e = n - k + 1;
        int nn[] = new int[n];
        int max[] = new int[e];
        int min[] = new int[e];
        for (int i = 0; i < n; i++) {
            nn[i] = sc.nextInt();
        }

        for (int i = 0; i < e; i++) {
            int temp[] = Arrays.copyOfRange(nn, i, i + k);
            max[i] = Arrays.stream(temp).max().getAsInt();
            min[i] = Arrays.stream(temp).min().getAsInt();
        }

        System.out.println(Arrays.toString(min));
        System.out.println(Arrays.toString(max));
    }
}

// 미닫이 창문 - C#
using System;
namespace Window
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("1. 배열의 크기 2. 창문의 크기");
            string select = Console.ReadLine();
            int size = int.Parse(select.Split(' ')[0]);
            int window = int.Parse(select.Split(' ')[1]);
            int[] home = new int[size];
            Console.WriteLine("순서대로 배열의 내용...");
            select = Console.ReadLine();
            for (int i = 0; i < size; i++)
                home[i] = int.Parse(select.Split(' ')[i]);
            int[] maxes = new int[size - window];
            int[] mins = new int[size - window];
            for (int i = 0; i < size - window; i++) 
            {
                int[] part = new int[window];
                Array.Copy(home, i, part, 0, window);
                int max = int.MinValue, min = int.MaxValue;
                foreach (int n in part)
                {
                    if (n < min)
                        min = n;
                    if (n > max)
                        max = n;
                }
                maxes[i] = max; mins[i] = min;
            }
            foreach (int n in maxes)
                Console.Write("{0} ", n);
            Console.WriteLine();
            foreach (int n in mins)
                Console.Write("{0} ", n);
            Console.WriteLine();
        }
    }
}

python 3.6 using zip, 입력은 범위내 random

구현

def sliding_window(lst, n):
    return (min(x) for x in zip(*(lst[i:] for i in range(n)))), (max(x) for x in zip(*(lst[i:] for i in range(n))))

입출력문

# Input  
from random import sample


arr_len, win_size = map(int, input().split())
arr = sample(range(-arr_len, arr_len), arr_len)
print(*arr, sep = ' ')

# Output
mn, mx = sliding_window(arr, win_size)

print(*mn, sep = ' ')
print(*mx, sep = ' ')

결과

>>>  
 8 3
-7 -1 7 -5 3 2 6 0

-7 -5 -5 -5 2 0
7 7 7 3 6 6

Python: BST 사용

from BST import BST

def sliding_window(arr, n, k):
    bst = BST()
    bst.addall(arr[:k])
    min = [bst.min()]
    max = [bst.max()]

    for i in range(1, n - k + 1):
        bst.add(arr[i+k-1])
        bst.remove(arr[i-1])
        min.append(bst.min())
        max.append(bst.max())

    return (min, max)

해놓고 보니 BST에서 중복 허용되게 바꿔야 정확하곘네요. 근데 기운이 없음T.T

BST 직접 만들어 봤는데 쉽게 봤다가 학을 뗐네요. 너저분합니다.

추가

bisect 모듈을 써서 고쳐볼까 찾아봤는데, 검색만 O(logN)입니다.

콤팩트하긴 하지만 리스트로 구현되어서 삽입이든 삭제(는 없지만)든 O(N)입니다.

class BSTNode:
    item = None
    left = None
    right = None

    def __init__(self, item):
        self.item = item
        self.left = None
        self.right = None


# 중복 허용 안 됨
class BST:
    root = None

    def __init__(self):
        root = None

    # __func/var: private, _func/var: protected
    # private 을 이렇게 쓰는 게 맞나..?
    # 찾고 있는 노드와 부모 노드를 같이 리턴하는 함수들. 있으면 편할까 싶었는데 어째 더 복잡해진 느낌

    def __find(self, p, t, x):   
        if not t:           return (p, None)
        elif x == t.item:   return (p, t)
        elif x < t.item:    return self.__find(t, t.left, x)
        else:               return self.__find(t, t.right, x)

    def __leftmost(self, p, t):
        if t.left:  return self.__leftmost(t, t.left)
        else:       return (p, t)

    def __rightmost(self, p, t):
        if t.right: return self.__rightmost(t, t.right)
        else:       return (p, t)


    #public functions
    def isempty(self):
        return self.root == None

    def max(self):
        if self.isempty(): return None
        (p, c) = self.__rightmost(None, self.root)
        return c.item if c else None

    def min(self):
        if self.isempty(): return None
        (p, c) = self.__leftmost(None, self.root)
        return c.item if c else None

    def find(self, x):
        if self.isempty(): return None
        (p, c) = self.__find(None, self.root, x)
        return c.item if c else None

    def add(self, x):
        if self.isempty():
            self.root = BSTNode(x)
            return True

        (p, c) = self.__find(None, self.root, x)
        if c: return False  # x already exists

        node = BSTNode(x)
        if x < p.item:  p.left = node
        else:           p.right = node
        return True

    def addall(self, lst):
        for item in lst:
            self.add(item)

    def remove(self, x): 
        (p, c) = self.__find(None, self.root, x)       
        if not c: return False  # empty or not found

        # leaf node
        if not c.left and not c.right:
            if p:   # c is not root
                if x < p.item:  p.left = None
                else:           p.right = None
            del c
            return True

        # non-leaf node
        if c.left:  # move rightmost node in left subtree of c
            (lp, lc) = self.__rightmost(c, c.left)
            if not lp:  pass                # lc is root
            if lp == c: lp.left = lc.left   # lc is direct child of c
            else:       lp.right = lc.left

            c.item = lc.item
            del lc
            return True

        else:       # move leftmost node in right subtree
            (rp, rc) = self.__leftmost(c, c.right)
            if not rp:  pass                # lc is root
            if rp == c: rp.right = rc.right # lc is direct child of c
            else:       rp.left = rc.right

            c.item = rc.item
            del rc
            return True

    def removeall(self, lst): 
        for item in lst:
            self.remove(item)

    def sorted(self):
        def trav(t):  #in-order
            if not t: return []
            return trav(t.left) + [t.item] + trav(t.right)
        return trav(self.root)

[n, k] = map(int, input('배열의 길이와 슬라이딩 윈도우의 길이를 나타내는 두 개의 정수n과 k:').split(' '))
arr = list(map(int, input('배열의 내용을 나타내는 n개의 정수:').split(' ')))
min1 = []
max1 = []
for i1 in range(k-1, n):
        arr1 = arr[i1-(k-1):i1+1]
        min1.append(str(min(arr1)))
        max1.append(str(max(arr1)))
print(' '.join(min1))
print(' '.join(max1))

package codingdojang;

import java.util.Scanner;

public class ex52 {

public static void main(String[] args) {
    // TODO Auto-generated method stub
    Scanner sc = new Scanner(System.in);

    int n = sc.nextInt();
    int k = sc.nextInt(); sc.nextLine();

    int arr[] = new int[n];

    for(int i=0; i<n; i++) {
        arr[i] = sc.nextInt();
    }


    sc.nextLine();

    for(int i=0; i<n-k+1; i++) {
        System.out.print(Math.min(Math.min(arr[i], arr[i+1]),arr[i+2])+" ");
    }

    System.out.println();

    for(int i=0; i<n-k+1; i++) {
        System.out.print(Math.max(Math.max(arr[i], arr[i+1]),arr[i+2])+" ");
    }

    System.out.println();
}

}

import java.util.Scanner;

public class level_3_sliding_window {

public static void main(String[] args) {

    System.out.println("배열의 길이와 슬라이딩 윈도우의 길이를 차례로 입력하세요.");
    Scanner sc = new Scanner(System.in);
    int arraysize = sc.nextInt(); // 배열의 길이.
    int[] array = new int[arraysize];
    int windowsize = sc.nextInt(); // 슬라이딩 윈도우의 길이.
    int[] window = new int[windowsize];
    int[] maxs = new int[arraysize - windowsize + 1]; // 최대값들을 저장할 배열.
    int[] mins = new int[arraysize - windowsize + 1]; // 최소값들을 저장할 배열.

    System.out.println("배열의 내용을 나타내는 정수값들을 입력하세요.");

    for(int i = 0; i < arraysize; i++) // 정수값들을 차례로 입력.
    {
        array[i] = sc.nextInt();
    }

    for(int i = 0; i < arraysize - windowsize + 1; i++) // 윈도우를 결정할 반복문 작성.
    {
        for(int j = 0; j < windowsize; j++)
        {
            window[j] = array[j + i];
            int max = window[0];
            int min = window[0];
        for(int h = 0; h < windowsize - 1; h++)
        {
            if(window[h + 1] > max)
            {
                max = window[h + 1];
            }
            if(window[h + 1] < min)
            {
                min = window[h + 1];
            }
            maxs[i] = max;
            mins[i] = min;
        }
        }
    }
    System.out.print("window의 최소값들 : ");
    for(int h = 0; h <maxs.length; h++)
    {
        System.out.print(mins[h] + "    ");
    }
    System.out.println();
    System.out.print("window의 최대값들 : ");
    for(int h = 0; h <maxs.length; h++)
    {
        System.out.print(maxs[h] + "    ");
    }
    sc.close();
}

}

파이썬 3.6

def sliding():
    length,k = map(int, input().split())
    source = input('').split()
    print("\n")
    print(' '.join([ min(source[i:i+3]) for i in range(len(source)-(k-1))]))
    print(' '.join([ max(source[i:i+3]) for i in range(len(source)-(k-1))]))

if __name__ == "__main__":
    sliding()

*결과값

8 3
1 3 -1 -3 5 3 6 7


-1 -1 -1 -3 3 3
3 3 5 5 6 7

입력 리스트 길이 1,000,000 슬라이드 길이 100,000일때 6초 내외로 걸립니다.

def window(a, n):
    maximums = list()
    minimums = list()
    maximums.append(max(a[:n]))
    minimums.append(min(a[:n]))
    maxcount = a[:n].index(maximums[0])
    mincount = a[:n].index(minimums[0])
    for i in range(len(a)-n):
        if maxcount:
            maximums.append(max(a[n+i], maximums[-1]))
            if maximums[-2] == maximums[-1]:
                maxcount -=1
            else:
                maxcount = n-1
        else:
            maximums.append(max(a[i+1:i+1+n]))
            maxcount = a[i+1:i+1+n].index(maximums[-1])
        if mincount:
            minimums.append(min(a[n+i], minimums[-1]))
            if minimums[-2] == minimums[-1]:
                mincount -=1
            else:
                mincount = n-1
        else:
            minimums.append(min(a[i+1:i+1+n]))
            mincount = a[i+1:i+1+n].index(minimums[-1])
    return maximums, minimums

import java.util.Arrays;
import java.util.Scanner;

public class SlidingWindow {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        String[] input = sc.nextLine().split(" ");
        int arrayLength = Integer.parseInt(input[0]);
        int windowLength = Integer.parseInt(input[1]);

        int[] array = new int[arrayLength];

        for(int i = 0; i< arrayLength; i++){
            array[i] = sc.nextInt();
        }
        int[] window = new int[windowLength];

        int[] minArray = new int[arrayLength - windowLength + 1];
        int[] maxArray = new int[arrayLength - windowLength + 1];

        for(int i=0; i< arrayLength - windowLength + 1 ; i++){
            window[0] = array[i];
            window[1] = array[i+1];
            window[2] = array[i+2];
            Arrays.sort(window);
            minArray[i] = window[0];
            maxArray[i] = window[2];
        }
        System.out.println(Arrays.toString(minArray));
        System.out.println(Arrays.toString(maxArray));
    }

}

  let exlist = [[8,3],[1, 3, -1, -3, 5, 3, 6, 7]]


  function window2 (x) {
    let a = [];
    let b = [];
    for (let i = 0; i < (x[0][0]- x[0][1]+1); i++) {
     a.push( x[1].slice(i,i+x[0][1]).reduce((acc,item) => acc > item ? item : acc))
     b.push( x[1].slice(i,i+x[0][1]).reduce((acc,item) => acc < item ? item : acc))
     }
     return [a,b]
}

console.log(window2(exlist))

// 자바입니다
public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        int n = Integer.parseInt(str[0]);
        int win2 = Integer.parseInt(str[1]);
        int win = 0;
        String[] numbers = br.readLine().split(" ");
        int[] nums = new int[n];
        for (int i=0; i<n; i++) {
            nums[i] = Integer.parseInt(numbers[i]);
        }

        int[] mins = new int[n-win2+1];
        int[] maxs = new int[n-win2+1];
        int t = win2;
        for (int i=0; i<n-t+1; i++) {
            int max = nums[i];
            int min = nums[i];
            for(int j=win; j<win2; j++) {
                max = Math.max(max, nums[j]);
                min = Math.min(min, nums[j]);
            }
            mins[i] = min;
            maxs[i] = max;
            win++;
            win2++;
        }
        System.out.println(Arrays.toString(mins));
        System.out.println(Arrays.toString(maxs));
    }

def sliding_window(n, k, array):
    minimum = []
    maximum = []
    for i in range(n - k + 1):
        minimum.append(min(array[i:i + k]))
        maximum.append(max(array[i:i + k]))
    return minimum + maximum
ans1 = [int(x) for x in input().split()]
ans2 = [int(y) for y in input().split()]
minmax = sliding_window(ans1[0], ans1[1], ans2)
for prt1 in minmax[:int(len(minmax)/2)]:
    print(prt1, end=' ')
print()
for prt2 in minmax[int(len(minmax)/2):]:
    print(prt2, end=' ')

#include <stdio.h>
#include <stdlib.h>

int main() {
    int length = 8,slid = 3, min, max;
    int ary[] = { 1, 3 ,-1 ,-3 ,5 ,3 ,6 ,7 };
    int *temp, *result;
    temp = (int *)malloc(slid * sizeof(int));
    result = (int *)malloc((length - slid + 1) * sizeof(int));

    for (int i = 0; i <= length - slid; i++) {
        for (int j = i; j < i + slid; j++) {
            temp[j - i] = ary[j];
        }
        min = max = temp[0];
        for (int j = 1; j < slid; j++) {
            min = min < temp[j] ? min : temp[j];
            max = max > temp[j] ? max : temp[j];
        }
        printf("%d ",min);
        result[i] = max;
    }
    printf("\n");
    for (int i = 0; i <= length - slid; i++) {
        printf("%d ", result[i]);
    }
    free(result);
    free(temp);
}

Python

n, k = 8, 3#n, k = map(int, input().split(" "))
arr = [1, 3, -1, -3, 5, 3, 6, 7]#list(map(int, input().split(' ')))
a = list()
b = list()
for i in range(len(arr)-k+1):
    a.append(min(arr[i:i+k]))
    b.append(max(arr[i:i+k]))
print(a)
print(b)

새로 들어오는 값과, 나가는 값, 직전의 min,max값
4가지 값을 비교하여 min,max를 구합니다.

n, k = map(int,input().split())
while 1:
    arr = list(map(int,input().split()))
    if len(arr) == n: break
    else: print('배열의 갯수가 틀립니다. 재입력 하세요.')

for i in range(n-k+1):
    tmp = arr[i:i+k]
    if i == 0: r = [( (min(tmp),max(tmp)) )]
    else:
        if r[-1][1] == arr[i-1]:
            if r[-1][1] < tmp[-1]: r.append( (r[-1][0],tmp[-1]) )
            elif r[-1][0] > tmp[-1]: r.append( (tmp[-1],max(tmp)) )
            else: r.append( (r[-1][0],max(tmp)) )
        elif r[-1][0] == arr[i-1]:
            if r[-1][0] > tmp[-1]: r.append( (tmp[-1],r[-1][1]) )
            elif r[-1][1] < tmp[-1]: r.append( (min(tmp),tmp[-1]) )
            else: r.append( (min(tmp),r[-1][1]) )
        else:
            if r[-1][0] > tmp[-1]: r.append( (tmp[-1],r[-1][1]) )
            elif r[-1][1] < tmp[-1]: r.append( (r[-1][0],tmp[-1]) )
            else: r.append( (r[-1][0],r[-1][1]) )

for j in range(2):
    for i in r:
        print(i[j],end=' ')
    print()

파이썬 3

def fn(k, list1):
    min_list = []
    max_list = []
    for i in range(len(list1) - k + 1):
        window = []
        for j in range(k):
            window.append(list1[i+j])
        min_list.append(min(window))
        max_list.append(max(window))

    return min_list, max_list

k = 3
list1 = [1, 3, -1, -3, 5, 3, 6, 7]

print(fn(k, list1)[0])
print(fn(k, list1)[1])

결과: k=3, list1 = [1, 3, -1, -3, 5, 3, 6, 7]

[-1, -3, -3, -3, 3, 3]
[3, 3, 5, 5, 6, 7]

=> core.

              1. 최대, 최소 구하기 =>> sorted()함수 사용 ==> max() & min()함수 사용

              2. window값이 몇 번 이동하는지 (반복을 위해서)

                       => 아래 그림을 보면 길이가 8인 배열에  크기가 3인 윈도우가 움직이는 걸을 가시화 함.

                            여기서 보면, 마지막 2개 뺴고는 각 배열의 요소들은 윈도우 첫 번째에 위치

                            즉, 윈도우의 맨 첫 번째 위치할 경우 == 윈도우 움직인 경우

                            ==> 윈도우의 첫 번째 위치로 선택받지 못하는 요소를 제외하면 윈도우의 이동 횟수가 나옴.

n,k = map(int, input().split(' '))
input_num = list(map(int,input().split(' ')))
cir = n-(k-1)
max_arr=[]
min_arr=[]
for i in range(cir):
    max_arr.append(max(input_num[i:i+k]))
    min_arr.append(min(input_num[i:i+k]))
print(min_arr)
print(max_arr)

C#

using System;
using System.Collections.Generic;
using System.Linq;

namespace CD052
{
    class Program
    {
        static void Main()
        {
            int[] inputSpec = Console.ReadLine().Trim().Split(' ').Select(s => int.Parse(s)).ToArray();
            int arrayLength = inputSpec[0];
            int windowLength = inputSpec[1];

            List<int> inputList = Console.ReadLine().Trim().Split(' ').Select(s => int.Parse(s)).ToList();

            DisplaySlidingMinMax(windowLength, inputList);
        }

        static void DisplaySlidingMinMax(int windowLength, List<int> inputArray)
        {
            Queue<int> window = new Queue<int>(inputArray.Take(windowLength - 1));
            List<int> maxValues = new List<int>();
            List<int> minValues = new List<int>();
            // sliding window 큐에 새로운 입력 배열의 다음 항목 enqueue, 기존 항목 dequeue
            // 최대, 최소값 확인
            for (int idx = windowLength - 1; idx < inputArray.Count; idx++)
            {
                window.Enqueue(inputArray[idx]);
                if (window.Count > windowLength) { _ = window.Dequeue(); }
                maxValues.Add(window.Max());
                minValues.Add(window.Min());
            }

            Console.WriteLine(string.Join(" ", minValues));
            Console.WriteLine(string.Join(" ", maxValues));
        }
    }
}

어렵습니다...

include

using namespace std;

int main(void){ //길이를 나타내는 n과 슬라이딩윈도우 사이즈를 나타내는 K int n,k;

cin >> n >> k;
//입력받은 배열. 
int arr[n];
for(int i=0;i<n;i++){
    cin >> arr[i];
}
//반복할 횟수 
int loop=n-k+1;
//윈도우가 움직일때마다 최대 최소값을 넣어줄 배열. 
int* maxArr=new int[loop];
int* minArr=new int[loop];
//윈도우의 처음과 끝을 알기위한 변수 
int first=0,last=k;
//윈도우가 움직이면서 최대최소값을 저장한다. 
for(int i=0;i<loop;i++){
    int max=0,min=9999;
    //윈도우내에서 최대/최소값을 찾는다. 
    for(int j=first;j<last;j++){
        if(max<arr[j])
            max=arr[j];
        if(min>arr[j])
            min=arr[j];
    }
    //찾은 값을 각 배열에 저장한다.
    maxArr[i]=max;
    minArr[i]=min;
    //윈도우를 한칸씩 옴긴다.
    first++;
    last++; 
}
//결과 출력 
for(int i=0;i<loop;i++){
    cout << minArr[i]<<' ';
}
cout<<endl;
for(int i=0;i<loop;i++){
    cout << maxArr[i]<<' ';
}
delete[] maxArr;
delete[] minArr;

}

def MAX(ary,index,W_l):
    max=ary[index]
    for i in range(index+1,index+W_l):
        if max<ary[i]:
            max=ary[i]

    return max
def MIN(ary,index,W_l):
    min=ary[index]
    for i in range(index+1,index+W_l):
        if min>ary[i]:
            min=ary[i]

    return min

N=int(input("배열 길이 : "))
W=int(input("윈도우 길이 : "))
ary=list(map(int,input("").split(" ")))
list_max=[]
list_min=[]
for i in range(N-W+1):
    list_max.append(MAX(ary,i,W))
    list_min.append(MIN(ary,i,W))
print("min :",list_min)
print("max :",list_max)

import timeit
import psutil

p = psutil.Process()
a, b = map(int, input('숫자 두 개를 입력하세요: ').split())
l = list(map(int,input('배열을 입력하세요 : ').split()))
start_time = timeit.default_timer() 
r = []
if a==len(l):
    i=0
    c=[]
    while i<=a-b:
        for w in range(b):
            c.append(l[i+w])
        r.append(max(c))
        i+=1
terminate_time = timeit.default_timer()
print("%f초 걸렸습니다." % (terminate_time - start_time)) 
print(p.memory_info())
print(r)

l = [1,3,-1,-3,5,3,6,7]
result = [],[]
for i in range(len(l)-2):
    Lmin = min(l[i:i+2])
    Lmax = max(l[i:i+2])
    result[0].append(Lmin)
    result[1].append(Lmax)
print(f'{result[0]}\n{result[1]}')

"""

from random import randint

n1 = int(input("배열의 길이를 입력하시오"))
n2 = int(input("슬라이딩 윈도우의 길이를 입력하시오"))

arr = [randint(-10,10) for _ in range(n1)]
print(arr)

max_arr=[]
min_arr=[]


for i in range(len(arr)-n2+1):
    max_arr.append(max(arr[i:i+n2]))
    min_arr.append(min(arr[i:i+n2]))

for k in max_arr:
    print(k,end=' ')
print('')
for k in min_arr:
    print(k,end=' ')

"""

min_list = []; max_list = []
nk = input()
n , k = nk.split(" ")
n = int(n); k = int(k)
arr = [int(i) for i in input().split(" ")]

for i in range(0,n-k+1):
  window = arr[i:i+k]
  min_list.append(min(window))
  max_list.append(max(window))

for i in min_list:
    print(i,end=' ')
print()
for i in max_list:
    print(i,end=' ')