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

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

프로그래머스

---

 

[ 정답 코드 & 올바른 풀이 ]

 

📌 올바른 풀이

 

 

중복되는 값을 제외해야 하므로 HashSet을 사용한다. 

 

길이가 1일때,

ele[0] / ele[1] / ele[2] / ele[3] / ele[4]

 

길이가 2일때,

ele[0] + ele[1] / ele[0] + ele[2] / ele[0] + ele[3] / ele[0] + ele[4]

ele[1] + ele[2] / ele[1] + ele[3] / ele[1] + ele[4] 

ele[2] + ele[3] / ele[2] + ele[4]

ele[3] + ele[4]

 

길이가 3일때,

ele[0] + ele[1] + ele[2] / ele[0] + ele[1] + ele[3] / ele[0] + ele[1] + ele[4]

ele[1] + ele[2] + ele[3] / ele[1] + ele[2] + ele[4]

ele[2] + ele[3] + ele[4] 

 

길이가 4일때,

ele[0] + ele[1] + ele[2] + ele[3] / ele[0] + ele[1] + ele[2] + ele[4]

ele[1] + ele[2] + ele[3] + ele[4]

 

위의 모든 경우의 수를 도출하기 위해서는 아래처럼 3중 for문을 돌려 현재인덱스 ~ 현재인덱스 + 길이전까지 각각의 합을 구해 반환하면 된다. 

        for(int i = 1; i <= elements.length; i++) {
            for(int j = 0; j < elements.length; j++) {
                int sum = 0;
                for(int z = j; z < j+i; z++) {
                    sum += elements[z % elements.length];
                }
                hs.add(sum);
            }
        }

 

** 이때, 그냥 z가 아닌 z % elements.length를 하는 이유는

길이가 5인 배열 [7, 9, 1, 1, 4]에서 j=4, i=3이라면(z = 4 ~ z = 6) 내부 반복문에서 ele[4] / ele[5] / ele[6] 이 되므로  ele[5] / ele[6]와 같이 기존 배열의 크기를 초과하게 된다. 

이를 방지하기 위해 z % elements.length를 하게 된다면,

ele[5%5] = 0 / ele[6%5] = 1 이 되므로 z가 배열의 범위를 벗어나도 원형 수열처럼 동작하도록 구현할 수 있다. 

 

---

📌 정답 코드

import java.util.*;

class Solution {
    public int solution(int[] elements) {
        int answer = 0;
        HashSet<Integer> hs = new HashSet<>();
        
        for(int i = 1; i <= elements.length; i++) {
            for(int j = 0; j < elements.length; j++) {
                int sum = 0;
                for(int z = j; z < j+i; z++) {
                    sum += elements[z % elements.length];
                }
                hs.add(sum);
            }
        }
        
        answer = hs.size();
        
        return answer;
    }
}