문제

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

---

입력

• 원형 수열의 모든 원소 elements

---

출력

• 원형 수열의 연속 부분 수열 합으로 만들 수 있는 수의 개수

---

풀이

제한조건

• 3 ≤ elements의 길이 ≤ 1,000
• 1 ≤ elements의 원소 ≤ 1,000

접근방법

자료구조 응용

구간 (a,b)만큼의 합을 만들었을 때, 서로 다른 수가 몇개 있는지 묻는 문제이다.
제한조건을 한 번 살펴보자.
elements의 길이가 최대 1000이다. 수가 충분히 작으므로 모든 경우를 세어보자.

우선 구간 (a,b)를 설정한다.
이때 수열이 원형으로 구성되어 있으므로, 인덱스 범위를 넘어 처음으로 다시 돌아올 수 있음에 유의하자.

구간을 설정하였으면, 해당 구간의 숫자들을 모두 더해주자.
여기서 중복되는 수가 발생할 수 있으므로, Set 자료구조를 이용해서 중복을 제거해주자.

Set에는 중복을 제외한 합들이 들어있기 때문에 결국 Set의 사이즈가 정답이 된다.

---

코드

import java.util.*;

class Solution {
    Set<Integer> set = new HashSet();
    public int solution(int[] elements) {
        for(int i = 0; i < elements.length; ++i) // 시작 숫자의 위치
            for(int j = 0; j < elements.length; ++j) // 시작위치부터 j개의 수를 확인
                set.add(getSum(i, j, elements));
        
        return set.size();
    }
    
    public int getSum(int start, int count, int[] elements){ 
    	// (start, start+count) 구간의 수를 모두 더한다.
        int sum = 0;
        for(int i = start; i < start+count; ++i)
            sum += elements[i % elements.length];
        return sum;
        
    }
}