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

LG CNS 코딩테스트 이후 하루에 한문제 정도 매일 꾸준히 알고리즘 공부하려고 하고있습니다!.

LG CNS 코딩테스트 후기는 예전 게시물에 올려두었습니다! 궁금하신분들은 한번 읽어보세요~~

 

본론

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

 

문제 설명

철호는 수열을 가지고 놀기 좋아합니다. 어느 날 철호는 어떤 자연수로 이루어진 원형 수열의 연속하는 부분 수열의 합으로 만들 수 있는 수가 모두 몇 가지인지 알아보고 싶어졌습니다. 원형 수열이란 일반적인 수열에서 처음과 끝이 연결된 형태의 수열을 말합니다. 예를 들어 수열 [7, 9, 1, 1, 4] 로 원형 수열을 만들면 다음과 같습니다.

 

원형 수열은 처음과 끝이 연결되어 끊기는 부분이 없기 때문에 연속하는 부분 수열도 일반적인 수열보다 많아집니다.
원형 수열의 모든 원소 elements가 순서대로 주어질 때, 원형 수열의 연속 부분 수열 합으로 만들 수 있는 수의 개수를 return 하도록 solution 함수를 완성해주세요.

 

문제 풀이

 

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

class Solution {
    public int solution(int[] elements) {
        int answer = 0;        
        Set<Integer> set = new HashSet<>();
                
        for(int i=1; i<elements.length+1; i++){ // 전체 개수 더하는 회전 수               
            for(int j=0; j<elements.length; j++) { // 실제 elements 요소
                
                int sum = 0;
                
                for(int k=0; k<i; k++){ // 실제 개수만큼 더하기
                   int index = (j+k) % elements.length;
                   sum += elements[index];
                }
                set.add(sum);
                
                
            }            
        }
        answer = set.size();
        return answer;
    }
}

위에 처럼 풀었습니다, Set Class는 중복을 허용 하지 않는 클래스입니다. 

 

처음 for문 원형 수열의 1개씩 더하고, 2개씩 더하고, 3개씩 더하고 전체를 한번에 더 할때 까지 for문을 돌립니다.

두번째 세번째 for문은 실제 1개씩 더 할때 , 2개씩 더할때 실제 값들의 합입니다.

변수 index는 해당 배열의 인덱스 값을 전체 길이의 length값으로 나눈 나머지를 가져옵니다. 이 이유는

절반이 이상 넘어가게될경우에는 원형 수열이기 때문에 다시 index가 0, 1 , 2 , 3, 4 ,5 이런 식으로 넘어가기 때문입니다.

그러면 배열의 인덱스 값을 초기화 됩니다.

 

주인장이 생각 하는 핵심 포인트

제가 생각하는 이문제의 핵심포인트는 index를 어떻게 만드냐인것 같습니다.

저부분을 생각하는데 2시간정도 소요 된거 같습니다. 처음에는 for문의로 별의 별짓을 다해고 했는데 제출 하면 12번째 15번째부터는 원형 수열의 개수가 많아지니 메모리나, 시간 때문에 불합격이 나오더라고요 ㅎㅎ

 

다른분들꺼는 더 좋게 잘푸시는 분들도 많으시더라고요,,, 저는 머리가 나빠서 이렇게 밖에는 저는 문제 제출후에 정답 맞으면 다른분들의 코드 보면서 공부하는 편인거 같습니다.

알고리즘 공부하면서 일하면서는 잘 안썼던 Class나 기능들을 많이 알게되면서 좋은거 같습니다.