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

백준을 둘러보던 중 수들의 합 2라는 문제는 찾게 되었다.

 

문제

이런 식으로 진행되는 간단한 문제인 듯했다.

근데 이거 그냥 단순히 차례대로 하나씩 값을 더해보면 되는 거 아닌가라고 생각하여

브루트 포스식(가능한 모든 경우의 수)으로 풀게 된다면 시간 초과가 날 것이다.

 

따라서 이 문제의 분류를 확인해 보니 투 포인터(Two-Pointer)로 분류가 된 것을 확인했다.

 

투 포인터(Two-Pointer)란

일차원배열에서 스타트 포인트와 엔드포인트를 두어 포인터를 옮겨가며 원하는 것을 찾아가는 형태이다.

이 때문에 투 포인터 알고리즘이라고 불린다.

 

풀이

프로그램이 시작되면 받은 값들을 이용하여 

배열의 처음부터 시작하여 값들을 확인하여 

 

두 포인터의 안의 값이

목표치보다 크다면

스타트 포인트를 옮겨서 

범위를 작게 조정하고,

 

목표치보다 작거나 같다면

엔드 포인트를 옮겨서

범위를 크게 조정하며 값들을 확인하는 방식이다.

 

또한

해당 값이 목표치와 일치한다면

출력할 값을 추가하는 방식으로 진행된다.

 

코드

import java.io.BufferedReader
import java.io.InputStreamReader

fun main(args: Array<String>) = with(BufferedReader(InputStreamReader(System.`in`))) {
    val (n, m) = readLine().split(" ").map { it.toInt() }
    val numberSet = readLine().split(" ").map { it.toInt() }

    var result = 0

    var startIndex = -1
    var endIndex = -1
    var sum = 0

    while (true) {
        if(endIndex == n - 1) {
            if(startIndex == n-1)
                break
            if(startIndex != n-1) {
                if(sum == m) result++
                startIndex ++
                sum -= numberSet[startIndex]
            }
        }
        else {
            if (sum < m) {
                endIndex ++
                sum += numberSet[endIndex]
            } else {
                if(sum == m) result++
                startIndex ++
                sum -= numberSet[startIndex]
            }
        }
    }
    println(result)
}

 

 

 

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

2003번: 수들의 합 2