Baekjoon 구간 합 구하기 4 문제를 풀면서 삽질하기

문제 링크 : https://www.acmicpc.net/problem/11659

 

처음 작성한 코드는 다음과 같고 결과는 시간 초과다.

fun main() {
    val countInput = readln().split(" ").last().toInt()
    val array = readln().split(" ").map { it.toInt() }.toIntArray()
    val sumArray = intArrayOf(0, *array)

    for (i in 1..array.size) {
        sumArray[i] = sumArray[i - 1] + sumArray[i]
    }

    for (i in 1..countInput) {
        val input = readln().split(" ").map { it.toInt() }.toIntArray()
        println(sumArray[input.last()] - sumArray[input.first() - 1])
    }
}

 

두 번째 코드는 테스트 통과(2840ms)다.

위 코드와 차이는 두 번째 for문에서 map으로 Int로 변환하고 다시 Int배열로 변환하는 불필요한 코드를 제거했다.

fun main() {
    val countInput = readln().split(" ").last().toInt() // 데이터의 개수, 질의 개수
    val array = readln().split(" ").map { it.toInt() }.toIntArray() // 구간 합을 구할 대상 배열
    val sumArray = intArrayOf(0, *array)

    for (i in 1..array.size) {
        sumArray[i] = sumArray[i - 1] + sumArray[i]
    }

    for (i in 1..countInput) {
        val input = readln().split(" ")

        println(sumArray[input[1].toInt()] - sumArray[input[0].toInt() - 1])
    }
}

 

세 번째 코드도 테스트 통과(2916ms)지만 위 코드보다 조금 느리다.

두 번째 코드에서 결과 출력할 때 타입을 변환하는 것보다 미리 변환하는 게 좋을 것 같아서였는데 오히려 더 느리다.

이 부분에서 이해가 가지 않는 게 map도 내부에 반복문(for)이 있고 toInt도 내부에 반복문(while)이 있는데 while이 for보다 더 빠를 수가 있냐는 것이다.

for는 정해진 횟수만큼 반복하고 while은 정해진 조건에 맞는지 체크하면서 반복하기 때문에 오히려 더 느리다고 생각했는데 결과를 보니 그게 아닌 것 같다. 

fun main() {
    val countInput = readln().split(" ").last().toInt() 
    val array = readln().split(" ").map { it.toInt() }.toIntArray() 
    val sumArray = intArrayOf(0, *array)

    for (i in 1..array.size) {
        sumArray[i] = sumArray[i - 1] + sumArray[i]
    }

    for (i in 1..countInput) {
        val input = readln().split(" ").map { it.toInt() }

        println(sumArray[input[1]] - sumArray[input[0] - 1])
    }
}

 

네 번째는 입력받은 문자열을 출력시 일부분을 변환하고 출력하는 방법으로 시도해 봤는데 IDE에서는 정상적으로 실행되고 디버그 모드로도 잘되는 걸 확인했는데 코드를 제출하니 런타임 에러 NumberFormatException와 ArrayIndexOutOfBounds가 발생했다. (이 부분은 원인을 모르겠다.)

fun main() {
    val countInput = readln().split(" ").last().toInt()
    val array = readln().split(" ").map { it.toInt() }.toIntArray()
    val sumArray = intArrayOf(0, *array)

    for (i in 1..array.size) {
        sumArray[i] = sumArray[i - 1] + sumArray[i]
    }

    for (i in 1..countInput) {
        val input = readln()

        println(sumArray[input[2].toString().toInt()] - sumArray[input[0].toString().toInt() - 1]) // NumberFormatException
        println(sumArray[Character.getNumericValue(input[2])] - sumArray[Character.getNumericValue(input[0]) - 1]) // ArrayIndexOutOfBounds
    }
}

 

다섯 번째는 입력을 받을 때 BufferedReader를 사용했고 테스트 통과(2372ms)로 더 빨라졌다.

 BufferedReader는 https://st-lab.tistory.com/41를 참고했다. (정말 잘 정리되어 있다.)

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))

    val countInput = br.readLine().split(" ").map { it.toInt() }
    val array = IntArray(countInput[0] + 1)

    val st = StringTokenizer(br.readLine())

    for (i in 1..countInput[0]) {
        array[i] = array[i - 1] + st.nextToken().toInt()
    }

    for (i in 1..countInput[1]) {
        val st = StringTokenizer(br.readLine())

        val i = st.nextToken().toInt()
        val j = st.nextToken().toInt()

        println(array[j] - array[i - 1])
    }
}

 

마지막으로 출력 부분도 BufferedWriter로 변경했는데 테스트 결과(728ms)가 나왔을 때 '와..' 할 수 밖에 없었다.

시간 차이가 이렇게 크게 날 줄은 몰랐다

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.*

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val countInput = br.readLine().split(" ").map { it.toInt() }
    val array = IntArray(countInput[0] + 1)

    val st = StringTokenizer(br.readLine())

    for (i in 1..countInput[0]) {
        array[i] = array[i - 1] + st.nextToken().toInt()
    }

    for (i in 1..countInput[1]) {
        val st = StringTokenizer(br.readLine())

        val i = st.nextToken().toInt()
        val j = st.nextToken().toInt()

        bw.write("${(array[j] - array[i - 1])}\n")
    }

    bw.flush()
    bw.close()
}

 

앞으로 코딩 테스트 문제를 풀 때 입출력은 무조건 BufferedReader / BufferedWriter다! 라고 했지만 잠깐 스치듯이 접하는 건 금방 잊어버리기에 내일은 BufferedReader / BufferedWriter에 대해 정리를 해야겠다.