투 포인터 (+ 백준 2003)

오늘은 투 포인터라는 개념을 알아보겠습니다!

투 포인터는 알고리즘.. 이라기보다는 개념이라고 하는게 더 맞는 표현인 것 같아요. 1차원 배열을 두고 start, end 라는 두 개의 인덱스를 사용해서 답을 구하기 때문에 Two Pointer (투 포인터) 라는 이름이 붙었습니다.

 

사실상 두 개의 인덱스 (포인터) 를 사용한다는 것 외에 특별히 설명할 수 있는게 없어서 오늘은 백준 2003번: 수들의 합 2 를 예시로 투 포인터를 설명해보려 합니다.

 

문제
N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력
첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.

출력
첫째 줄에 경우의 수를 출력한다.

 

 

만약 예를 들어 N이 5, M이 2 라고 할 때, 주어진 배열이 [5, 5, 1, 1, 1]이라면 아래와 같은 동작방식이 수행될 것입니다.

 

sum이 M보다 크다면 start를 옮기면서 sum에서 기존의 start자리에 있던 값을 빼주고,

sum이 M보다 작거나 같다면 end를 옮기면서 sum에 새로운 end자리에 있는 값을 더해줍니다.

그리고 만약 같을 경우에는 answer를 증가시켜주면 됩니다.

 

 

아래는 인덱스 변수를 사용한 투포인터 방식으로 작성한 전체 코드 입니다. (시간: 12ms)

let inputs = readLine()!.split(separator: " ").map { Int(String($0))! } // [N, M]
let list = readLine()!.split(separator: " ").map { Int(String($0))! } // 입력 배열

var start = 0
var end = 0
var sum = list[0]
var answer = 0

while start < list.count && end < list.count {
    if sum > inputs[1] {
        sum -= list[start]
        start += 1
        continue
    }
    if sum == inputs[1] { answer += 1 }
    end += 1
    if end < list.count { sum += list[end] }
}

print(answer)