[BOJ] 1895번: 필터

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

 

 

문제

숫자 9개가 오름차순이나 내림차순으로 정렬되어 있을 때, 중앙값은 다섯 번째 숫자이다. 예를 들어, 1, 3, 4, 1, 2, 6, 8, 4, 10의 중앙값은 4이다. (1 ≤ 1 ≤ 2 ≤ 3 ≤ 4 ≤ 4 ≤ 6 ≤ 8 ≤ 10)

이미지 I는 크기가 R × C인 2차원 픽셀이다. (3 ≤ R ≤ 40, 3 ≤ C ≤ 40) 각 픽셀은 어두운 정도 V를 나타낸다. (0 ≤ V ≤ 255)

중앙 필터는 이미지에 있는 노이즈를 제거하는 필터이다. 필터의 크기는 3 × 3이고, 이미지의 중앙값을 찾으면서 잡음을 제거한다.

예를 들어, 아래와 같은 6 × 5 이미지가 있다.

필터링된 이미지의 크기는 4 × 3이고, 아래와 같다.

 

가장 왼쪽 윗 행에 필터를 두고, 오른쪽으로 움직이면서 중앙값을 찾는다. 한 행을 모두 이동했으면, 다음 행으로 이동해 다시 중앙값을 찾는다. 아래와 같은 순서를 가진다.

 

위의 그림에서 각각의 중앙값은 36, 36, 21이 된다. 이 값은 필터링된 이미지 J의 첫 행과 같다.

이미지 I가 주어졌을 때, 필터링 된 이미지 J를 구하고, 값이 T보다 크거나 같은 픽셀의 수를 구하는 프로그램을 작성하시오.

예를 들어, T = 40일 때, 위의 예에서 정답은 7이다. 

 

-> 문제 설명: 이미지를 통해 이해해보자면, 주어진 I에 대하여 3x3 크기로 I를 순회하며 각 크기에 대한 중앙값을 J에 저장하는 것이다.

 

풀이

r, c = map(int, input().split())
li = [list(map(int, input().split())) for _ in range(r)]
t = int(input())
J = []

for i in range(r - 2):
    for j in range(c - 2): #왼쪽끝점
        filter = []
        for k in range(i, i + 3):
            for l in range(j, j + 3):
                filter.append(li[k][l])
        J.append(sorted(filter)[4])

print(sum(1 for i in J if i >= t))

 

1. r, c를 입력받고 I를 입력받아 이차원배열 li에 저장한다. 

2. t를 입력받고 J를 저장할 리스트를 생성한다.

3. 왼쪽 끝점이 될 수 있는 범위인 r-2, c-2에 대해 반복문을 돌린다.

4. 왼쪽 끝점 i, j에 대하여 3x3 크기의 모든 요소를 순회하고, 해당 값을 filter에 삽입한다.

5. 리스트 filter에 있는 모든 9개의 요소에 대하여, 중앙값(= 정렬했을 때 4번째 인덱스)을 J에 삽입한다.

6. J에서 t보다 큰 요소의 개수를 계산하여 출력한다.