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

알고리즘 풀이 방법입니다.
문제(Problem) -> 생각(Think) -> 해결책(Solution) -> 리뷰(Review) 를 통해서 정리해서 작성합니다.

Problem📄

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

프로그래머스

---

Think🤔

 

문제가 나와있는대로 먼저 작성

 

7,9,1,1,4

길이가 1인 것
1,1,4,7,9 -> 중복제거 1,4,7,9
길이가 2인 것 
[1,1][1,4][4,7][7,9][9,1] -> 중복제거 -> 2,5,11,16,10
길이가 3인 것
[7,9,1][9,1,1][1,1,4][1,4,7][4,7,9] -> 중복제거 -> 17,11,6,12,20
... 반복

 

규칙이 이런식으로 반복됨

 

중복을 제거하고 (Set 이용)

 

원형수열의 특징 2배를 만들어서 포인터 이동시키면서 각 수열의 합을 구함

1,2,3,4,5,1,2,3,4,5

1,2,3,4,5,1,2,3,4,5

1,2,3,4,5,1,2,3,4,5

1,2,3,4,5,1,2,3,4,5

1,2,3,4,5,1,2,3,4,5

...

이런식으로 반복 시켜서 확인

---

Solution✍

 

import java.util.Set;
import java.util.HashSet;

class Solution {
    public int solution(int[] elements) {
        int answer = 0;
        
        int[] cirele = new int[elements.length * 2];
        
        //01234
        //56789
        for(int i=0; i<elements.length; i++){
           cirele[i] = elements[i];
           cirele[i + elements.length] = elements[i];
        }

        // 원순열 특징이용해서 자리값 맨처음으로 돌리면서 
        // 각 자리값 합으로 만들 수 있는 경우의 수 구함
        // 7 9 1 1 4 들어올 시
        // 7이 맨앞이면서 9114 더해준값
        // 9맨 앞 더 해준 값 해서 4까지
        Set<Integer>set = new HashSet();
        for(int i=0; i<elements.length; i++){
            int sum = 0;
            for(int j=i; j<elements.length + i; j++){
                sum += cirele[j];
                set.add(sum);
            }
        }
        
        return set.size(); // 중복없는 총 사이즈 값
    }
}

---

Review🤩

 

중복수열 풀이에 대해 알아보았다.

처음에는 중복수열 자체도 몰라서 해당 알고리즘 관련 다른 글들을 많이 참조했음

---