[A&I Code Camp] Day27 (+ 속도개선)

✍   Kotlin을 PS 문제 풀기

소속중인 A&I 동아리에서 코딩역량을 강화하고자
코딩캠프를 진행하며 작성한 포스트입니다.
해당 포스트는 kotlin을 기반으로 작성합니다.

누적합

이번 주 주제는 누적합 알고리즘이며
백준에 하루 한 문제를 풀어가며 작성할 것입니다.
누적합 알고리즘
해당 내용은 위 포스트에 작성하였습니다.

16507번

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

이 문제는 2차원 배열에서 (r1, c1)부티 (r2, c2)까지의 평균을 문제입니다.

Solve

1. 미리 숫자를 받아 2차원 누적합 배열을 만든다. 대신 크기는 +1씩을 해서 인덱스로 활용하기 쉽게 만든다.
2. 반복 q만큼 반복을 돌려 좌표를 받아주고 2중 반복문을 통해 좌표끼리의 숫자 갯수를 구해준다.
3. 그 뒤 좌표까지의 합을 불러오고 count에 나눠준다.

import java.io.StreamTokenizer

fun main() = with(StreamTokenizer(System.`in`.bufferedReader())){
    fun nextInt() : Int {
        nextToken()
        return nval.toInt()
    }

    val r = nextInt(); val c = nextInt(); val q = nextInt();

    val pSum = Array(r+1) { IntArray (c+1) { 0 } }

    repeat(r){idx ->
        repeat(c) {jdx ->
            pSum[idx+1][jdx+1] = pSum[idx + 1][jdx] + pSum[idx][jdx + 1] - pSum[idx][jdx] + nextInt()
        }
    }

    val sb = StringBuilder()
    repeat(q){
        val r1 = nextInt()
        val c1 = nextInt()
        val r2 = nextInt()
        val c2 = nextInt()

        var count = 0

        for(idx in r1..r2){
            for(jdx in c1 .. c2){
                count+=1
            }
        }

        sb.appendLine((pSum[r2][c2] - pSum[r2][c1-1] - pSum[r1-1][c2] + pSum[r1-1][c1-1]) / count)
    }
    println(sb)
}

+속도 개선

1. 이중 반복문으로 cnt를 받다보니 넓이를 구할 때 속도가 늦어지게 되는데
   이것을 (r2-r1+1) * (c2-c1+1)으로 미리 직사각형의 넓이를 구해서 나눠주면 속도가 개선된다.
2. 또 repeat문에서 값 인자를 idx, jdx에서 i, j로 짧게 바꾸면 그것 또한 속도가 개선된다.

fun main() = with(StreamTokenizer(System.`in`.bufferedReader())){
    fun nextInt() : Int {
        nextToken()
        return nval.toInt()
    }

    val r = nextInt(); val c = nextInt(); val q = nextInt();

    val pSum = Array(r+1) { IntArray (c+1) { 0 } }

    repeat(r){i ->
        repeat(c){j->
         pSum[i+1][j+1] = pSum[i+1][j] + pSum[i][j+1] - pSum[i][j] + nextInt()
        }
    }

    val sb = StringBuilder()
    repeat(q){
        val r1 = nextInt()
        val c1 = nextInt()
        val r2 = nextInt()
        val c2 = nextInt()
        //직사각형 넓이 구하는 공식
        val sq = (r2-r1+1) * (c2-c1+1)
        sb.appendLine((pSum[r2][c2] - pSum[r2][c1-1] - pSum[r1-1][c2] + pSum[r1-1][c1-1]) / sq)
    }
    println(sb)
}

1. 첫 제출
2. 이중반복으로 넓이 구하던 것을 sq 한 식으로 바꿈
3. repeat문의 인자를 짧게 바꿈.

📌 결론

누적합 알고리즘의 이론을 공부해서 정리해 두어야 될 것 같다.