[PS] 1806) 부분합

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

1806번: 부분합

Gold4) 1806.부분합

 

• 누적합, 두 포인터

누적합으로 처음에 코딩을 구성했지만 각 구간을 탐색하는 과정에서 for문을 두번 돌아 O(n^2)의 시간이 걸려 시간 초과가 났다. 시간을 줄이기 위해 두 포인터를 이용하여 코드를 다시 구성했다.

 

입력으로 받은 배열을 유지하며, 특정 값과 구간 합을 비교하므로 구간을 줄이고 늘리는 것으로 결과에 도달할 수 있어 두 포인터를 사용하여 깔끔하게 코드를 구성할 수 있다.

문제 풀이의 핵심 과정은 다음과 같다.

1. lp, rp 를 0, 0으로 초기화한다.
2. rp를 증가시키고 구간 합을 구한다.
3. 구간 합 > S(문제에서 제시해준 값) 이면 lp를 증가시킨다.
4. 이때 lp를 증가시키기 전 구간에 대한 정보를 통해 최소의 구간인지 확인하고 갱신한다.
5. 구간 합 < S 이면 rp를 증가시킨다.

위의 과정을 코드로 작성하면 다음과 같다.

def tp(board, n, s) :
        lp, rp = 0, 0
        tmpsum = board[rp]
        minval = n+1
        while True :
            # print(lp,rp,tmpsum, end=' ')
            if tmpsum < s :
                rp += 1
                if rp == n :
                    break
                tmpsum += board[rp]
            else :
                if lp == rp :
                    minval = 1
                    break
                else :
                    if rp - lp + 1 < minval :
                        minval = rp - lp + 1
                    lp += 1
                    tmpsum -= board[lp-1]
        if minval == n+1 :
            minval = 0
        return minval

정답률이 25%로 높지 않은데 시간복잡도를 다루는 것이 까다로워서 그런 것 같다. 위의 코드로 작성하면 총 2*N만큼 코드가 수행되어 O(N)의 시간복잡도로 문제를 해결할 수 있다.