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

✴️ 문제

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

 

 

 

 

✴️ 문제 풀이

 

중복되는 값을 제외하기 때문에 Set을 사용해야한다.

 

연속되는 수열을 구하는 방법을 생각해보면

elements 배열의 (0 ~ 0), (0 ~ 1) , (0 ~ 2), (0 ~ 3), (0 ~ 4)의 합을 구해서 set에 추가해주면 된다.

 

합을 구하는 과정에서 두가지 방법이 있는데

입력받은 elements를 2배의 형태로 만들어서 사용하거나,

%를 사용해 순환인덱스로 조회하는 방법을 사용할 수 있다.

 

정석적인 방식은 %를 사용하는 방식이 아닐까싶다

실제로 시간을 보면 더 빠르긴하다

 

✴️ 전체 코드 (Java)

 

1. 배열 크기를 2배로 늘려서 사용한 경우

import java.util.*;

class Solution {
    public int solution(int[] elements) {        
        Set<Integer> set =  new HashSet<>();
        ArrayList<Integer> nums = new ArrayList<>();
        for(int i=0; i<2; i++){
            for(int j : elements){
                nums.add(j);
        	}
        }
        
        
        for (int i = 0; i < elements.length; i++) {
            for (int j = 1; j <= elements.length; j++) {
                List<Integer> subList = nums.subList(i, i+j);
                
                int sum = 0;
                for (int num : subList)
                    sum += num;
                set.add(sum);
            }
        }
        return set.size();
    }
}

 

 

2. %를 사용한 순환구조

import java.util.*;

class Solution {
    public int solution(int[] elements) {        
        Set<Integer> set =  new HashSet<>();
        
        int cnt = 1;
        while (cnt <= elements.length) {
            for (int i = 0; i < elements.length; i++) {
                int sum = 0;
                for (int j = i; j < i + cnt; j++) {
                    sum += elements[j % elements.length];
                }
                set.add(sum);
            }
            cnt++;
        }
        return set.size();
    }
}