[Kotlin] 백준 2015번 - 수들의 합4

 

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

2015번: 수들의 합 4

유형

누적합, Map 자료구조

풀이 과정

1. 누적합을 저장할 배열(accSum[])과 각 누적합의 개수를 카운트 할 Map(accSumMap)을 선언한다.
2. 누적합을 모두 구한다.
3. 누적합을 차례대로 확인한다. (accSum[1..n])
   1. 누적합(accSum[i])이 k(target)와 일치하면 정답 카운트를 증가시킨다
   2. accSum[i]에서 뺀 값이 k가 되는 누적합의 개수 즉, 앞에서 기록했던 누적합 카운트에서 accSumMap[accSum[i] - k]의 개수만큼 정답 카운트를 증가시킨다. (answer += accSumMap[accSum[i] - k])
   3. accSumMap에 accSum[i]의 개수를 반영한다. (accSumMap[accSum[i]] += 1)

코드1

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

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val (n, target) = readLine().split(" ").map(String::toInt)
    val nums = IntArray(n + 1)
    val accSum = IntArray(n + 1)        // accSum[i]: nums[1] + ... + nums[i]
    val accSumMap = HashMap<Int, Int>() // 누적합의 개수 저장
    var answer = 0L

    // 누적합 계산
    val st = StringTokenizer(readLine())
    for (i in 1..n) {
        nums[i] = st.nextToken().toInt()
        accSum[i] = accSum[i - 1] + nums[i]
    }

    for (i in 1..n) {
        if (accSum[i] == target) answer++ // 0~i번째 까지의 누적합이 target과 같은지 검사

        // 앞서 저장한 누적합 중 accSum[i]에서 빼면 target이 되는 것의 개수
        val prevSumCount = accSumMap.getOrDefault(accSum[i] - target, 0)
        answer += prevSumCount
        accSumMap[accSum[i]] = accSumMap.getOrDefault(accSum[i], 0) + 1 // 누적합 개수 추가
    }

    println(answer)
}

코드2 (간결한 버전)

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

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val (n, target) = readLine().split(" ").map(String::toInt)
    val nums = IntArray(n + 1)
    val accSum = IntArray(n + 1) // num[1..i]까지의 누적합 저장
    val accSumMap = HashMap<Int, Int>() // 누적합의 개수 저장
    var answer = 0L

    // 누적합 계산
    val st = StringTokenizer(readLine())
    for (i in 1..n) {
        nums[i] = st.nextToken().toInt()
        accSum[i] = accSum[i - 1] + nums[i]
    }

    accSumMap[0] = 1 // accSum[i] == target인 경우를 대비
    for (i in 1..n) {
        // 앞서 저장한 누적합 중 accSum[i]에서 빼면 target이 되는 것의 개수를 더한다
        answer += accSumMap.getOrDefault(accSum[i] - target, 0)
        accSumMap[accSum[i]] = accSumMap.getOrDefault(accSum[i], 0) + 1
    }

    println(answer)
}

피드백

배열에 음,양수가 함께 있을 때는 특정 부분합을 찾기 위한 알고리즘으로 투포인터를 사용하지 않는다. 왜냐하면, 포인터를 움직였을 때 합이 증가할지 감소할지 알 수 없기 때문이다.