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

문제 출처

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

프로그래머스

걸린 시간

07:52 ~ 09:20 // 소요 시간 1시간 28분 ( 생각하다가 사이트 참고 ) 

피드백

문제를 너무 어렵게 생각하는 것 같음. 

보편화 딱 시키고 바로 코드화 시켜야지 으이!

다른 사이트 세곳 참고 

https://hstory0208.tistory.com/entry/Java자바-프로그래머스-Lv2-연속-부분-수열-합의-개수-Set

[Java/자바] 프로그래머스 Lv2 - 연속 부분 수열 합의 개수 (Set)

 

https://velog.io/@sugyeonghh/프로그래머스-연속-부분-수열-합의-개수Java

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

https://velog.io/@jp-share/코딩테스트-프로그래머스-연속-부분-수열-합의-개수-Java

[코딩테스트] 프로그래머스 - 연속 부분 수열 합의 개수 (Java)

처음 문제 봤을 때 이거 첫 Sum 구해서 앞에 원소 뺴고 뒤에 원소 더해서 개수 체크하면 

시간 복잡도 줄이겠다 생각을 했다. 

 

구현을 1시간 20분 하다가 포기하고 사이트를 참고 했다.

 

세 곳 모두 성능 안 나올 것 같은 느낌의 코드가 있길래 

정답에 초점을 뒀구나 싶었음. 

( for 문 세개는 내가 알고리즘 문제 풀 때 금기시하는... ) 

 

사이트에서 아이디어를 가져와서 내가 처음 생각한 로직을 적용해봤다.

첫번째 이미지가 내 소스코드

 

 

코딩테스트 에서도 마찬가지 겠지만 

내가 문제 풀 때 가장 중요하게 생각하는 건

주어진 조건에 맞게 시간 안에 문제를 풀었는가? 뿐 이다. 

위의 조건이 모두 맞았을 경우에 "잘" 풀었는가 의미 있게 되는 것이다. 

 

째든 나의 우선순위를 충족 시킨 위의 모든 코드가 멋진 코드이다.

 

문제

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

원형 수열은 처음과 끝이 연결되어 끊기는 부분이 없기 때문에 연속하는 부분 수열도 일반적인 수열보다 많아집니다.

원형 수열의 모든 원소

elements

가 순서대로 주어질 때, 원형 수열의 연속 부분 수열 합으로 만들 수 있는 수의 개수를 return 하도록 solution 함수를 완성해주세요.

제한 사항

• 3 ≤ elements의 길이 ≤ 1,000
• 1 ≤ elements의 원소 ≤ 1,000

예시

입출력 예 #1

길이가 1인 연속 부분 수열로부터 [1, 4, 7, 9] 네 가지의 합이 나올 수 있습니다.

길이가 2인 연속 부분 수열로부터 [2, 5, 10, 11, 16] 다섯 가지의 합이 나올 수 있습니다.

길이가 3인 연속 부분 수열로부터 [6, 11, 12, 17, 20] 다섯 가지의 합이 나올 수 있습니다.

길이가 4인 연속 부분 수열로부터 [13, 15, 18, 21] 네 가지의 합이 나올 수 있습니다.

길이가 5인 연속 부분 수열로부터 [22] 한 가지의 합이 나올 수 있습니다.

이들 중 중복되는 값을 제외하면 다음과 같은 18가지의 수들을 얻습니다.

[1, 2, 4, 5, 6, 7, 9, 10, 11, 12, 13, 15, 16, 17, 18, 20, 21, 22]

수도코드

없음.

소스 코드 ( 자세한 내용 주석 참고 )

import java.util.*;
class Solution {
    public int solution(int[] elements) {
        int answer = 0;
        
        Set<Integer> sumSet = new HashSet<>();
        
        int length = elements.length;
        // 1 ~ elements.length 의 개수 만큼 for 문 ( 1개인 case , 2개인 케이스 , ... , elements.lenght 개 인 케이스)
        // 시작점 정해주는 for 문
        // sum 구하는 for문
        // 삼중 포문 이거 케이스 적어서 할 수 있지 
        // 케이스 10배만 많아도 이중 배열로 탐색 성능 올려야될 것 같은데...
        for( int size = 1; size <= length ; size ++ ){
            int sum = 0;
            int start = 0;
            // 첫 케이스
            for( int i = 0; i < size ; i++ ){
                sum += elements[i];
            }
            sumSet.add(sum);
            
            while( start < length - 1 ){
                // sum 에서 빼고 
                sum -= elements[start];
                // 새로 추가되는 녀석 추가
                // 최대 길이가 넘어가면 다시 0으로 돌아오게 MOD 연산
                sum += elements[(start+size)%length];
                // 시작점 옮기기
                start++;
                // 새로운 총합 추기
                sumSet.add(sum);
            }
        }
        answer = sumSet.size();
        return answer;
    }
}