[백준 2003번] [Kotlin] 수들의 합 2

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

2003번: 수들의 합 2

 

난이도 : 실버 4
태그 : 브루트포스, 두 포인터

 

 

설명

특정 구간이 주어지는 m과 같은 케이스를 구하는 문제입니다.

두 포인터를 사용해 풀 수 있을 것 같네요.

 

 

소스코드

import java.util.*

fun main() = with(System.`in`.bufferedReader()) {
    val (n, m) = readLine().split(" ").map { it.toInt() }
    val st = StringTokenizer(readLine())
    val arr = Array(n) { st.nextToken().toInt() }

    var left = 0
    var right = 1
    var sum = arr[0]
    var cnt = 0

    while (true) {
        if (sum == m) {
            cnt++
            sum -= arr[left++]
        } else if (sum < m) {
            if (right == n) break
            sum += arr[right++]
        } else {
            sum -= arr[left++]
        }
    }

    println(cnt)
}

 

코드분석

1. left, right 포인터를 선언 및 0, 1로 초기화, sum은 arr[0]으로 초기화
2. 무한루프를 돌며 sum이 m과 같아지면 카운트를 1 증가시키고, 합에서 왼쪽 포인터를 뺌
3. sum이 m보다 작다면 오른쪽 포인터를 더하고, 포인터를 1 증가시킴.
   1. right 배열이 맨 끝에 도달하여 배열 범위를 벗어나면 반복문 탈출
4. sum이 m보다 크면 왼쪽 포인터를 삭제하고, 왼쪽 포인터를 1 증가시킴