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

//연속 부분 수열만을 다룬다.
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int solution(int[] elements) {
        int answer = 0;
        int count = elements.length;
        int[] list = new int[count * 2];
        Set<Integer> numSet = new HashSet<>();
        
        for(int i = 0; i < count; i++) {
            list[i] = elements[i];
            list[i + count] = elements[i];
        }
        
        while(count > 0) {
            int sumLength = elements.length - count;
            
            for(int i = 0; i < elements.length; i++) {
                int sumNum = 0;
                
                for(int j = i; j <= i + sumLength; j++) {
                    sumNum += list[j];
                }
                
                numSet.add(sumNum);
            }
            
            count--;
        }
        
        answer = numSet.size();
        
        return answer;
    }
}

 

풀이

1. 연속된 수를 만들기 위해서 뒤에 같은 길이의 수들을 붙여준다. (이게 은근히 코딩테스트 문제에서 많이 쓰이는 것 같다.)

2. 그리고 elements.length만큼만 사용해서 반복되기 이전의 수들까지만 사용한다. 73114 73114 일때 다시 뒤의 7부터 계산은 필요X

3. 3의 길이일 때 7+3+1, 3+1+1, 1+1+4, 1+4+7, 4+7+3 이렇게 계산 11 5 6 12 14 이런 수들의 합을 set에 저장해서 값들이 겹치지 않게 모두 보관해서 set의 길이를 제출한다.

 

느낀점

sumNum += elements[j % elements.length];

%으로 나머지 계산을 해서 list를 따로 만들지 않게 하는 방법도 있지만 코드가 간편해지지만 그만큼 계산을 많이하게되어 계산 시간이 길어진다. list를 따로 사용할 때는 메모리를 그만큼 사용한다. 근데 list의 크기가 최대 1000 * 2로 그리 크지 않기에 상관없어보인다.

%계산으로 list를 대체했을 때

list로 새로 만들어주었을때

상황에 따라서 맞춰서 사용하는 편이 좋아보인다.

 

 

 

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

프로그래머스