[백준 / Python] #1895 필터

문제

 

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

1895번: 필터

---

Algorithm

주어진 배열을 입력받아 3*3내에서의 T값보다 크거나 같은 것의 개수를 출력하면 된다. 주어진 배열이 40이하의 자연수 이므로 최대 38*38개수의 필터가 있고, 필터 내에서 중앙값을 구하는데, 이때 9개의 원소를 정렬하는 것이므로 9log9정도의 시간복잡도를 가진다.  38*38*9log9 = 약12996이므로 브루트포스로 풀 수 있다고 생각했다!

먼저 배열의 크기 R,C를 입력받은 후에 배열의 원소를 입력받고, T값을 입력받는다. 3*3필터를 적용하기 위해 반복문을 실행해서 그 안의 원소들을 arr에 append하고, arr을 정렬해준다.  9개의 원소의 중앙값은 arr[4]이므로 arr4가 T보다 크면 cnt에 더해주고 마지막으로 cnt를 출력해주면 된다!

 

---

 

 

Code

input = __import__('sys').stdin.readline

r,c = map(int,input().split())
arr=[]
temp = []
for i in range(r):
    arr.append([*map(int,input().split())])

t = int(input())
cnt=0

for i in range(r-2):
    for j in range(c-2):
        temp.append(arr[i][j])
        temp.append(arr[i][j+1])
        temp.append(arr[i][j+2])
        temp.append(arr[i+1][j])
        temp.append(arr[i+1][j+1])
        temp.append(arr[i+1][j+2])
        temp.append(arr[i+2][j])
        temp.append(arr[i+2][j+1])
        temp.append(arr[i+2][j+2])
        temp.sort()
        if temp[4] >= t:
            cnt+=1
        temp=[]
print(cnt)