프로그래머스 : 연속 부분 수열 합의 갯수 ( LV 2 )

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

프로그래머스

 

* 원형으로 구현된 배열의 모든 연속된 부분 집합의 갯수들을 구하는 문제.

* 아이디어는 생각해냈지만 구현 방법에서 막혀서 답을 보았습니다.

* 필자의 아이디어

 - 우선 Set<> 자료구조를 사용해서 최종 결과를 반환한다.

 - Queue<> 자료구조를 사용해서 길이가 2인 부분 집합의 갯수를 구하려면 2번 pop() 하고 순서대로 2번 push() 하는 방법을 

파라미터인 elements 길이만큼 진행하는 것이다. 3일때도 4일때도 마찬가지.

 - 2번, 3번 pop() 하고 push()를 elements[] 길이만큼 진행한다는 코드 구현이 생각나지 않았다.

 

* 답안 아이디어

 - Set<> 자료구조를 사용하는것은 똑같다.

 - for() 한번 더 사용해서 첫번째 for()의 변수번 만큼 값을 더해준다. 

 - 원형 배열이니 순환을 위해서 % elements.length 붙여서 인덱스를 초기화 시켜준다.

 

아래는 구현 코드이다.

 

import java.io.*;
import java.util.*;

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

 

 * 3중 for() 루프가 핵심이다.

 * 첫 for() 루프는 연속된 부분집합의 길이를 결정하는 index이다.

 * 두번째 for() 루프는 전체 elements[] 배열을 순환하는 index이다.

 * 세번째 for() 루프는 i 번 만큼. 즉 i 길이만큼 더하는 것이다.

 * 마지막으로 %size 연산을 함으로서 원형 배열을 완성시켜준다.

 * 여기서 핵심은 세번째 for() 에서 i 만큼 부분집합의 길이를 만들어주고 % 연산으로 원형을 연결시켜주는 것이다.

 * 다음 원형 배열이 나올때 아이디어를 생각하면 금방 풀 수 있을것이다.