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

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

프로그래머스

Lv2. 중에서도 쉬운 문제

 

내 풀이

1. 원래 배열 길이의 두 배의 길이 배열에 원소들 한 번 더 저장

2. 자료구조 HashSet을 사용해 중복저장을 피함

3. size 별로 차례대로 합을 구한 뒤 set에 저장

4. set의 size 리턴

import java.util.*;

class Solution {
    public int solution(int[] elements) {
        int answer = 0;
        int length = elements.length;
        int[] twice_elements = new int[length*2];
        
        for(int i=0; i<length; i++){
            twice_elements[i] = twice_elements[i+length] = elements[i];
        }
        HashSet<Integer> set = new HashSet<>();
        for(int s=1; s<=length; s++){ // 부분수열의 길이
            for(int i=0; i<length; i++){ // 덧셈 시작 인덱스
                int sum = 0;
                for(int j=i; j<i+s; j++){ // 덧셈 로직
                    sum+=twice_elements[j];
                }
                set.add(sum);
            }
        }
        answer = set.size();
        return answer;
    }
}

 

 

다른 사람 풀이

모드 연산을 사용하면 불필요한 메모리 사용을 줄일 수 있었다.

import java.util.*;

class Solution {
    public int solution(int[] elements) {
        Set<Integer> set = new HashSet<>();

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

        return set.size();
    }
}