프로그래머스 Lv4 - 안티세포

문제 해석

임의의 숫자들을 원소로 갖는 배열 b가 존재하고, b[i] 가 속하는 집합을 X X의 가장 좌측 원소의 바로 왼쪽에 있는 원소를 포함하는 집합을 Y라고 할 때 sum(X) = sum(Y) 가 성립하면, X, Y를 합칠 수 있다.

배열 c를 선언하고

i = 0 으로 설정하고

b[i]가 속한 X, b[i]의 좌측 첫번째 원소가 속한 Y에 대해 Sum(X), Sum(Y)를 구한다.
Sum[X] == Sum[Y]가 성립하면 두 집합을 합치거나, 합치지 않을 수 있다.
합치는 연산을 수행하면 c에 i를 추가하고 1로 돌아간다.
합칠 수 없거나, 합치지 않는다면 i의 값을 1 증가 시키고 1로 돌아간다.

문제 풀이

단순화

i는 합치기 연산을 수행할 때 합치기에 사용한 b의 마지막 원소 인덱스를 저장한다.
b[i]는 항상 양수이다.
또한 Sum(X) = Sum(Y)는 같은 값을 가지고 있다.
i는 증가하는 방향으로만 구성된다.

위 네 특성으로 인해서 c를 구성하는 원소들은 절대로 중복되지 않는다.

예를 들어 [1, 1, 1, 1] 을 보자 [[1, 1], [1, 1]]에 해당하는 c는 무엇일까? [[1,1], [1,1]]은 c = [1, 3] 외엔 존재 하지 않는다 [[1], [1,1], [1]] 은 c = [2] 밖에 없다. [[1, 1, 1, 1]] 은 c = [2, 4] 밖에 없다.

이 특성을 관찰하여 살펴보았다면, c는 그저 원소를 묶은 방법을 표기하는 방식일 뿐이고 우리가 구해야하는 것은 원소를 합칠 수 있는 경우의 수를 구하는 것이다.

접근

b[0]	b[1]	b[2]	b[4]
1	1	1	1

초기 b 배열의 모습을 그려두었다. 여기서 b[0]까지만 고려할 떄 만들 수 있는 경우의 수는 몇개일까? 답은 공집합, 1개이다. b[0]은 좌측에 아무 원소도 없기 때문에 주어진 연산을 수행할 수 없어 c = [] 이 될 것이다. b[1] 까지 고려했을 때는 몇개가 될 것인가? c = [[], [1]] 이 될 것이다. 각 각 [1, 1] 인 상태와, [[1, 1]] 인 상태를 나타낸다. 이 떄 나오는 패턴들을 F[i]라고 하자

F[1] = [ [1, 1], [[1, 1]] ]

F[2] = [ [1, 1, 1],  ## F[1][0] 에 1을 추가한 형태
         [[1, 1], 1], ## F[1][1] 에 1을 추가한 형태
         [1, [1, 1]] ]

F[3] = [ [1, 1, 1, 1],  ## F[2][0] 에 1을 추가한 형태
         [1, 1, [1, 1]], 
         [1, [1, 1], 1], ## F[2][2] 에 1을 추가한 형태
         [[1, 1], 1, 1], ## F[2][1] 에 1을 추가한 형태
         [[1, 1], [1, 1]], 
         [[1, 1, 1, 1]] ]

이렇게 될 것이다.

여기서 합쳐진 원소들의 집합 X, Y의 합을 잘 살펴보면 2의 제곱수에 해당한다는 것을 눈치챌 수 있다. 당연하게도, sum[X] == sum[Y] 이 성립해야 합칠 수 있기 때문에 합친 후의 값은 y x 2^x 꼴이 될 것이다. F[i] 를 구성하는 원소 중 합쳐진 집합이 있다면 그 집합의 합은 b[i] x 2^x 꼴이 된다는 말이다.

또한 F[i+1]의 원소는 F[i]의 원소에 b[i]를 이어붙인 형태가 되는 패턴을 포함하는 것을 확인할 수 있다.

그러면 새로 추가된 패턴들은 어떤 것인가? F[i+1]에 새로 추가된 패턴은 F[i]의 끝 패턴이 단일 원소로 끝나고, 거기에 이어붙인 1을 가지고 합치기 연산을 수행할 수 있는 경우에 생기는 패턴들이다.

여기서 이 문제가 부분 최적 문제에 해당함을 알 수 있다. 따라서 다이나믹 프로그래밍을 고려할 수 있다.

그러면 어떠한 경우에 합치는 것이 가능한 것인지 생각해보자.

$b[i]$ 가 $b[i-1]$ 을 포함한 집합 $Y$ 와 합쳐졌다는 것은, 위에 언급했듯 $b[i] * 2^x$ 의 꼴을 갖추는데 성공했다는 말이다. $b[i]$ 를 포함한 집합 X 합이 $b[i] * 2^x$ 라면 $b[i-1]$ 을 포함한 집합 Y의 합은 $b[i] * 2^{x-1}$ 이 되어야 한다는 말이다.

그럼 이를 기반으로 점화식을 추론하기 위한 기본 전제 조건들을 적어보자

dp[i][j] => b[0] 부터 b[i] 까지만 고려했을 때, $b[i]$ x $2^j$ 의 형태를 만들 수 있는 경우의 수

dp[0][0] = 1 이다. (공집합)
dp[i][0] = Σdp[i-1] 이다.
b[i]를 마지막 원소로 포함하는 집합 X과, X의 첫번째 원소 좌측에 위치한 원소를 포함하는 Y의 합이 같아야한다. `

2번 조건은 dp[i]를 단독으로 둘 경우에 해당 한다. 즉 Sum(X) = b[i]에 해당하는 경우이며, 이 때는 b[i]를 제외한 다른 원소들을 묶는 모든 방법에 b[i]를 붙이기면 되기 때문에 2번 조건이 성립한다.

3번 조건은 수식으로 표현을 하면 다음과 같다.

$X = \{b[j], b[j+1], ... , b[i]\}$ $Y = {b[k]. .., b[j-1]}$ $\Sigma(X) = ΣY$

여기서 매 계산마다 합을 구할 순 없으니, 이럴 때 사용하기 좋은 누적합을 정의하자

psum[i+1] = psum[i] + b[i]

psum[0] = 0

또한 3번 조건의 세분화를 위해 아래와 같이 정의하자.
$yLast = Y$ 를 구성하는 원소의 마지막 인덱스
$leftLast = Y$ 의 첫번째 원소 좌측에 있는 남은 원소들 중 가장 오른쪽에 있는 원소 인덱스

이 때 아래와 같은 조건을 만족해야한다. ${psum[i]} - b[i]*2^{j-1} = psum[yLast]$ 를 만족하는 ${yLast}$ 가 존재한다. ${b[yLast] * 2^{k} = b[i]*2^{j-1}}$ 를 만족하는 $k$ 가 존재한다. (단 $k>0$ ) ${psum[yLast] - psum[leftLast] = b[i] * 2^{j-1}}$ 를 만족하는 $leftLast$ 가 존재한다.

위 세 조건을 만족해야 dp[i][j] 가 존재할 수 있다.
1번 조건은 간단하게, 현재 만들려는 수가 $b[i]*2^{j}$ 라면,
X의 합이 $b[i]*2^{j-1}$ 이 되어야 하는 것이고
2번 조건은 $Y$ 의 합은 $b[yLast] * 2^k$ 형태가 되어야 하기 때문에 k가 존재해야한다.
3번 조건은 $Y$ 역시 $X$ 의 합과 같은 값을 가져야 하기 때문에 위 조건이 성립해야한다.

이를 표로 나타내면 다음과 같다.

0	...	leftLast	...	yLast	...	i
남은		영역	Y	Y	X	X

이제 생각해보자. $b[0]$ ~ $$b[i $]$ 만 고려하고 있는 상황에서 $b[i] * 2^{j}$ 형태를 만드는 경우의 수는 무조건 $b[i]*2^{j-1}$ 을 만드는 경우의 수가 포함되어 있어야만 가능하다.
위 표를 살펴보면 Y의 영역과 X의 영역은 고정되어버리기 때문에, 결국 $dp[i][j]$ 는 $b[0]$ ~ ${b[leftLast]}$ 의 영역에서 원소들을 합치는 경우의 수와 동일하다는 것을 알 수 있다.

이를 기반으로 최종적으로 정리를 하면 아래와 같다.

$dp[i][j]$ 가 존재하려면 $dp[i-1][j] > 0$ 을 만족해야 한다. $psum[i] - b[i]*2^{j-1} = psum[yLast]$ 를 만족하는 $yLast$ 가 존재해야 한다. $b[yLast] * 2^{k} = b[i]*2^{j-1}$ 를 만족하는 $k$ 가 존재해야 한다. 단 ${k>0}$ $psum[yLast] - psum[leftLast] = b[i] * 2^{j-1}$ 를 만족하는 $leftLast$ 가 존재해야 한다. $dp[i][j] = \Sigma_{l_=0}^{n}dp[leftLast][l], n = log_2( max(psum))$

이를 코드로 옮기면 답을 얻을 수 있다.

소스코드

import kotlin.math.*;

class Solution {
    
    val MOD = (1e9+7).toInt()
    
    fun prefixSum(arr: IntArray): LongArray {
        val psum = LongArray(arr.size + 1)
        psum[0] = 0
        
        for(i in 1..arr.size) {
            psum[i] = psum[i-1] + arr[i-1]
        }
        
        return psum
    }
    
    fun parametricSearch(arr: LongArray, target: Long): Int {
        var left = 0
        var right = arr.size-1
        
        while(left <= right) {
            val mid = left + (right-left)/2
            
            if(arr[mid] < target) {
                left = mid + 1
            } else if(arr[mid] == target) {
                return mid
            } else {
                right = mid - 1
            }
        }
        
        return -1
    }
    
    fun partialSolution(b: IntArray, bLen: Int): Int {
        val psum = prefixSum(b)
        val limit = ceil(log(psum[psum.size-1].toDouble(), 2.0)).toInt()
        val dp = Array(bLen){IntArray(limit+1)}
        
        dp[0][0] = 1
        
        if(bLen == 1) {
            return dp[0][0]
        }
        
        for(i in 1 until bLen) {
            dp[i][0] = dp[i-1].reduce{a, b -> (a+b)%MOD}
            
            for(j in 1..limit) {
                
                if(dp[i][j-1] == 0) {
                    continue
                }
				val half = b[i] * 2.0.pow(j-1).toLong()
                var target = psum[i+1] - half
                val yLast = parametricSearch(psum, target) - 1
                
                if(yLast < 0) {
                    continue
                } 
                
                val k = (j-1) + log(b[i].toDouble()/b[yLast] , 2.0)
                
                if(k != k.toInt().toDouble()) {
                    continue
                }
                
                if(k < 0) {
                    continue
                }
                
                if(dp[yLast][k.toInt()] <= 0) {
                    continue
                }
                
                target = psum[yLast+1] - half
                val leftLast = parametricSearch(psum, target)
                
                if(leftLast < 0) {
                    continue
                }
                
                if(leftLast == 0) {
                    dp[i][j] = 1
                    continue
                } 
                
                dp[i][j] = dp[leftLast-1].reduce {a, b -> (a+b)%MOD}
            }
        }

        return dp[bLen-1].reduce{a,b -> (a+b)%MOD};
    }
    
    fun solution(a: IntArray, s: IntArray): IntArray {
        var answer: IntArray = IntArray(s.size)
        
        var lastOffset = 0
        for(i in 0 until s.size) {
            val b: IntArray = a.sliceArray(lastOffset .. lastOffset+s[i] - 1)
            answer[i] = partialSolution(b, s[i])
            lastOffset += s[i]
        }
        
        return answer
    }
}

후기

최근 집안 일이 대충 정리되고 나서 재취업을 준비하면서 코딩 테스트를 준비하다가 여러 개의 알고리즘을 사용해서 풀 수 있는 문제 유형을 찾다보니 Lv4 문제까지 풀게 되었다. 이 문제는 동적 계획법, 누적합, 이진 탐색(Parametric Search) 를 이용해서 풀었는데 경우에 따라서는 트리 구조도 이용할 수 있을 것 같다. 다만 이 경우 이전 상태에 대한 관리가 필요하기 때문에 메모리를 굉장히 많이 사용하게 될 것 같아 고민하다 위 풀이 방법을 떠올렸는데 풀고나서 유사한 풀이들이 보여 확인해보니 프로그래머스 공식 블로그에 해설로 굉장히 유사한 풀이가 있었다. 다만 읽고 있는데 수식을 틀리게 적어놓은 부분이 보여서 해당 글을 읽고 접근 하는 사람들은 좀 헤메지 않을까 싶은 생각이 들었다.

[프로그래머스] Lv4 - 안티 세포

프로그래머스 Lv4 - 안티세포

문제 해석

문제 풀이

단순화

접근

소스코드

후기