연속 부분 수열 합의 개수 (자바, Java)

오랜만에 알고리즘 풀이를 작성한다.

저번 공지대로, 백준허브를 통해 github에 자동커밋으로 기록하고 있었으나...

이 부분은 리뷰 사항을 블로그에 남기는 것이 적절하다 판단하여 작성하게 되었다.

 

처음에 바보같이 백트래킹으로 불려고 하다가,

백트래킹의 대표적 문제인 N-Queen 문제가 정답률 나락간거보고..아니다 싶어서

좀 더 단순하게 생각해서 풀었다.

배열의 순번에 나머지를 넣어서 연속순환시키자!

나와 비슷하게 푼 사람들이 대다수 있었다.

import java.util.*;

class Solution {

    static Set<Integer> set;
    static int el;

    public int solution(int[] elements) {
        set = new HashSet<>();
        el = elements.length;

        for (int i=0; i<el; i++) {
            for (int j=1; j<=el; j++) {
                set.add(sum(elements, i, j));
            }
        }
        return set.size();
    }

    public int sum(int[] elements, int start, int l) {
        int sum = 0;
        for (int i=start; i<start+l; i++) {
            sum+=elements[i%el];
        }
        return sum;
    }
}

아무생각없이 매서드를 빼버렸는데, 이것도 백트래킹으로 풀려고 했던 관성의 흔적.

그냥 3중포문으로 처리해주면 된다.

 

아무튼 문제가 뭐냐...이 경우, 부분수열의 길이가 늘어날때마다 기존 데이터를 계속해서 계산해주어 중복계산하는 문제가 생긴다.

예시의 테스트케이스는 길이가 5밖에 안되서 별로 티가 안난다. 하지만, 문제 조건에서 주어진 배열의 길이는 1000이나 된다. 심각한 비효율을 야기한다.

 

아니나 다를까, 동적계획법으로 푼 풀이가 있었다.

 

import java.util.*;

class Solution {
        public int solution(int[] elements) {
            Set<Integer> set = new HashSet<>();
            int[] dp = new int[elements.length];
            for(int len = 1;len <= elements.length; len++){
                for(int i = 0;i<elements.length;i++){
                    dp[i] += elements[(len+i-1)%elements.length];
                    set.add(dp[i]);
                }
            }
            return set.size();
        }
    }

각 시작원소 지점에 따라 dp 배열로 메모이제이션을 한 뒤,

길이만 하나씩 늘려가면서, 새로이 들어오는 원소들만 하나씩 더해주면 끝.

두 코드를 직접 돌려보면 아시겠지만, 성능 차이가 어마어마하게 난다.

아는 이론을 문제에 적용하지 못해 참으로 분했다.

분한 마음을 못 이기고, 이렇게 기록을 남긴다.