[알고리즘] 프로그래머스 - 연속 부분 수열 합의개수 Lv2 Java

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

프로그래머스

 

package Programmers;

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

public class 연속부분수열합의개수 {
    public static void main(String[] args){
        연속부분수열합의개수 T = new 연속부분수열합의개수();
        int[] elements = {7, 9, 1, 1, 4};
        T.solution(elements);
    }

    public int solution(int[] elements) {
        int answer = 0;
        //7 9 1 1 4  7 9 1 1 4
        int[] myElements = new int[elements.length * 2];
        //elements 를 두번 넣어준다.
        int cnt = 0;
        for (int i = 0; i < 2; i++) {
            for (int iArr: elements) {
                myElements[cnt++] = iArr;
            }
        }
        Set<Integer> sumSet = new HashSet<>();
        //길이가 1 ~ elements 인 연속 부분수열을 구하자.
        //window 개수
        for (int i = 1; i <= elements.length; i++) { //window 갯수
            for (int s = 0; s < elements.length; s++) { //시작점의 위치 s
                int sum = 0;
                for (int j = s; j < s+i; j++) { // 시작점 부터 window 개수만큼 반복
                    sum += myElements[j];
                }
                sumSet.add(sum);
            }
        }
        answer = sumSet.size();
        return answer;
    }
}

1. 전체적인 풀이법 

  1.1  ) 입출력 예제를 보면 굉장히 친절함, 구할수있는 조합은 SlidingWindow 로 영역을 1 ~ elements 길이 만큼 쳐주면 된다. 

   ex )

int[] elements = {7, 9, 1, 1, 4};

window = 1

7

9

1

1

4

window = 2

7,9

9,1

1,1

1,4

window = 3

7,9,1

9,1,1

1,1,4

1,4,7

4,7,9

............

결국 나올수있는 조합수는 elements 길이만큼 window 쳐주면된다. 

그럼 결국 코드로 어떻게 반복시키냐 문제인데 최대로 돌수있는 경우는 elements 만큼 배열을 한번더 반복해주면 된다.

 

2. 풀이 

   2.1 myElements 배열 생성 ( elements ) 배열을 한번더 반복 해준 배열

   2.2 3중for문 생성 

   2.3 window 의 개수만큼 반복할 for문 1개

   2.4 시작점의 위치를 잡아줄 s for문 1개

   2.5 시작점 부터 window 길이만큼 반복할 for문 1개 

   2.6 window길이만큼 반복했으면 Set에 집어넣는다 (중복제거)

   2.7 전부다 돌았으면 Set의 크기를 answer 에 대입