[PRG] 131701 연속 부분 수열 합의 개수 JAVA

https://school.programmers.co.kr/learn/courses/30/lessons/131701

프로그래머스

 

메모리: 80.8 MB

실행시간: 13.27 ms

 

문제분석

배열 길이가 최대 2000(n), 나올 수 있는 부분 수열 길이가 1000(m) 이므로
누적합을 활용해 문제를 풀면 효율을 높일 수 있다 !

※ 시간 복잡도 O(nm)

이때, 중복 제거를 위해 두 가지 방법으로 경우의 수를 저장할 수 있다.

1. boolean배열을 통해 경우의 수 체크
2. HashSet을 통해 중복 제거

예상으로는 HashSet을 사용할 경우 효율이 떨어질 것으로 생각된다 (메모리를 많이 쓰게 됨)
두 가지 코드를 모두 작성한 뒤 효율체크 해보겠슴당 !

 

걸린시간

30분 ⏱️

 

풀이방법

1. 길이 3배 배열 생성 (원형 배열 구현을 위해 length * 2, 누적합 저장을 위해 + length)
2. 누적합 저장
3. HashSet 생성 || boolean 배열 생성
4. 1 ~ element.length 까지 부분 수열 합 저장
5. 결과 반환

 

포인트

원형 배열이기 때문에 길이를 두배 늘려줘야 모든 경우의 수를 체크할 수 있다 !

 

코드

1. boolean 배열을 사용한 경우

class Solution {
    public int solution(int[] elements) {
        // 누적합 저장 배열 선언 (원형 배열 구현을 위해 elements.length * 2, 누적합 저장을 위해 + elements.length)
        long[] prefixSum = new long[elements.length * 3 + 1];
        // 누적합 저장
        for(int i = elements.length; i < prefixSum.length; i ++) {
            prefixSum[i] = prefixSum[i - 1] + elements[i % elements.length];
        }
        // 중복 제거를 위해 boolean배열에 체크
        boolean[] checked = new boolean[1000 * 1000 + 1];
        // 1 - element.length 까지 부분 수열 합 구하기
        for(int i = 1; i <= elements.length; i ++) {
            for(int j = elements.length; j < prefixSum.length; j ++) {
                checked[(int) (prefixSum[j] - prefixSum[j - i])] = true;
            }
        }
        // 체크된 경우 카운트
        int answer = 0;
        for(int i = 0; i < checked.length; i ++) {
            if(checked[i]) answer ++;
        }
        // 결과값 반환
        return answer;
    }
}

 

2. HashSet을 사용한 경우

import java.util.*;

class Solution {
    public int solution(int[] elements) {
        // 누적합 저장 배열 선언 (원형 배열 구현을 위해 elements.length * 2, 누적합 저장을 위해 + elements.length)
        long[] prefixSum = new long[elements.length * 3 + 1];
        // 누적합 저장
        for(int i = elements.length; i < prefixSum.length; i ++) {
            prefixSum[i] = prefixSum[i - 1] + elements[i % elements.length];
        }
        // 중복 제거를 위해 해시셋에 부분 수열 합 저장
        HashSet<Long> hSet = new HashSet<>();
        // 1 - element.length 까지 부분 수열 합 구하기
        for(int i = 1; i <= elements.length; i ++) {
            for(int j = elements.length; j < prefixSum.length; j ++) {
                hSet.add(prefixSum[j] - prefixSum[j - i]);
            }
        }
        // 해시셋 사이즈 반환
        return hSet.size();
    }
}

 

두 가지 코드의 효율을 체크해 본 결과

 

1. boolean 배열 사용 - 메모리: 80.8 MB, 시간: 13.27 ms   ⭕

2. HashSet 사용 - 메모리: 141 MB, 시간: 100.73 ms         ❌