백준 1895 필터 Kotlin (완전 탐색)

문제 출처 : https://www.acmicpc.net/problem/1895

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이다. 

입력

첫째 줄에 이미지의 크기 R과 C가 주어진다. 그 다음 R개의 각 줄에는 C개의 픽셀 값이 주어진다. 마지막 줄에는 T값이 주어진다.

출력

첫째 줄에 필터링 된 이미지 J의 각 픽셀 값 중에서 T보다 크거나 같은 것의 개수를 출력한다.

알고리즘 분류

• 브루트포스 알고리즘
• 정렬

풀이

6개월 전 NumberFormatException 때문에 질문 올려놓고 까먹고 있던 문제에 어제 어떤 분이 댓글 달아주셔서 다시 푼 문제.

가끔 입력값에 맨 앞이나 맨 뒤에 쓸데없는 공백이 들어가 BufferReader로 받고 split하는 과정에서 NumberFormatException이 뜨는 경우가 있다. 이 경우 입력 문자열에 trim()을 사용하면 문자열의 앞과 뒤의 공백을 제거해준다.

 

문제 풀이는 다음과 같다.

음.. 그냥 문제에서 요구하는대로 r-3, c-3 크기의 2차원 배열 Filter를 만들어주고 

i -> 0 .. r-3

j -> 0 .. c-3

을 순회하며 filter[i][j] = graph[i + 0..2][j + 0..2] 중의 5번째 값을 넣으면 된다.

이렇게 만들어진 filter[i][j]에 대해 T보다 크거나 같은 원소의 개수를 출력하면 된다.

본인은 filter.flatMap { it.asIterable() }.count { it >= search } 이렇게 구해줬는데

filter를 2차원 배열로 만들고 다시 평탄화해서 count함수를 쓸 바에 애초에 filter 배열을 1차원 배열로 만들어도 됐을 것 같다는 생각이 이제야 든다. 

코드

val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().trim().split(' ').map { it.toInt() }
fun getInt() = br.readLine().trim().toInt()

lateinit var graph: Array<List<Int>>

fun makeFilter(r: Int, c: Int): Array<IntArray> {
    val filter = Array(r - 2) { IntArray(c - 2) }
    for (i in 0..r - 3) { // == filter.indices
        for (j in 0..c - 3) { // filter[i].indices
            val list = IntArray(9)
            var idx = 0
            for (rr in 0 until 3) {
                for (cc in 0 until 3) {
                    list[idx++] = graph[i + rr][j + cc]
                }
            }
            filter[i][j] = list.sorted()[4]
        }
    }
    return filter
}

fun main() = with(System.out.bufferedWriter()) {
    //input
    val (r, c) = getIntList()
    graph = Array(r) { getIntList() }
    val search = getInt()

    //solve
    val filter = makeFilter(r, c)

    //만들어진 필터에서 search보다 큰 개수 찾기
    //output
    write("${filter.flatMap { it.asIterable() }.count { it >= search }}")
    close()
}