[파이썬 알고리즘 문제풀이 입문] 탐색&시뮬레이션 - 수들의 합 (투포인터 알고리즘)

*문제 본문은 강의 내용과 관련되어 있어 자세하게 적지 않았습니다.

 

 

 

문제

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

 

 

 

풀이

• 답안 : Python

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
A = list(map(int, input().split()))

lt = 0
rt = 1
total = A[0]
count = 0

while True:
    if total < M: # total이 부분합보다 작을 때
        if rt < N: # rt가 끝까지 도착 안했을 때
            total += A[rt]
            rt += 1
        else:
            break # rt가 끝까지 도착했을 때
            
    elif total == M: # total이 부분합이랑 같을 때
        count += 1
        total -= A[lt]
        lt += 1
        
    else: # total이 부분합보다 클 때
        total -= A[lt]
        lt += 1
        
print(count)

• 답안 : Kotlin (내가 바꿔본 것 / 정확X)

 

import java.io.*
import java.util.*

fun main(args: Array<String>) = with(BufferedReader(InputStreamReader(System.`in`))){
    var (N, M) = readLine().split(" ").map { it.toInt() }
    var A = readLine().split(" ").map { it.toInt() }

    var lt = 0
    var rt = 1
    var total = A[0]
    var count = 0

    while(true) {
        if(total < M) {
            if(rt < N) {
                total += A[rt]
                rt += 1
            } else {
                break
            }
        } else if (total == M) {
            count += 1
            total -= A[lt]
            lt += 1
        } else {
            total -= A[lt]
            lt += 1
        }
    }

    println(count)
}

- 처음 문제 풀 때 생각했던 방법은, 2개 → 3개 → 4개 → ... 이런식으로 묶인 개수 별로 합을 비교하는 방법으로 생각했었던 것 같다.

- 답안에서는 포인터를 활용하여 접근을 하고 있었고, 이것을 '투 포인터 알고리즘' 이라고 부른다고 한다.

   → 리스트에 순차적으로 접근해야 할 때, 두 개의 위치를 기록하면서 처리 (부분 연속 수열 찾기)
- lt : 시작점 / rt : 끝점 / total : 부분합 / count : 부분합이 3이 되었을 때를 카운팅한 개수

- total이 M보다 작을때, 같을 때, 클 때 → 3가지로 경우의 수로 나누어서 생각해야 한다.

- rt가 끝까지 도착했을 때 (N보다 크거나 같을 때) break로 while문을 멈춘다.