[프로그래머스] 연속 부분 수열 합의 개수 - Java

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

프로그래머스

 

⭐️ 중요 포인트

1. 일단 3중 포문을 사용해서 완탐으로 문제를 해결할 수 있다.

2. 그러나 완탐으로 해결하게 되면 중복된 경우(startIdx가 0부터 시작해서 len이 1, 2, 3, ..., n까지라고 할 때 (1), (1+2), (1+2+3), ... 처럼)가 계산된다.

3. 문제는 해결되지만 좀 더 빠른 방법으로 구현하기 위해서 elements의 길이만큼 cache를 선언하여 누적합을 구해 set에 넣으면 중복을 줄일 수 있다.

(0번째 인덱스에는 7부터 시작하는 누적합, 1번째 인덱스에는 9부터 시작하는 누적합을 구하며 len까지 누적하여 set에 넣으면 2중 for문안에 문제를 해결할 수 있고, set을 통해 누적합의 중복을 방지할 수 있다.)

 

 

<DP 해결>

import java.util.*;

class Solution {
    
    static int[] elements;
    static int answer;
    
    static Set<Integer> hash;
    static int[] cache;
    
    void init(int[] elements) {
        this.elements = elements;
        this.answer = 0;
        
        hash = new HashSet<>();
        cache = new int[elements.length];
    }
    
    void solve() {
        
        for (int len = 1; len <= elements.length; len++) {
            for (int idx = 0; idx < elements.length; idx++) {
                cache[idx] += elements[(idx + len - 1) % elements.length];
                hash.add(cache[idx]);
            }
        }
        
        answer = hash.size();
    }
    
    
    public int solution(int[] elements) {
        init(elements);
        solve();
        return answer;
    }
}

 

<완탐 해결>

import java.util.*;

class Solution {
    
    static int[] elements;
    static int answer;
    
    static Set<Integer> hash;
    
    void init(int[] elements) {
        this.elements = elements;
        this.answer = 0;
        
        hash = new HashSet<>();
    }
    
    void solve() {
        
        for (int cnt = 1; cnt <= elements.length; cnt++) {
            for (int startIdx = 0; startIdx < elements.length; startIdx++) {
                int sum = 0;
                for (int idx = startIdx; idx < startIdx + cnt; idx++) {
                    sum += elements[(idx) % elements.length];
                }
                hash.add(sum);
            }
        }
        
        answer = hash.size();
    }
    
    
    public int solution(int[] elements) {
        init(elements);
        solve();
        return answer;
    }
}