문제

• 어떤 자연수로 이루어진 원형 수열의 연속하는 부분 수열의 합으로 만들 수 있는 수가 모두 몇 가지인지 구하고자 한다.
  • 원형 수열이란 일반적인 수열에서 처음과 끝이 연결된 형태의 수열을 말합니다.

    • 예를 들어 수열 [7, 9, 1, 1, 4] 로 원형 수열을 만들면 다음과 같습니다.

      

  • 원형 수열의 모든 원소 elements가 순서대로 주어질 때, 원형 수열의 연속 부분 수열 합으로 만들 수 있는 수의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항

입력

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

출력

• 원형 수열의 연속 부분 수열의 합의 개수

코드

import java.io.*;
import java.util.*;
class Solution {
    public int solution(int[] elements) {
        int n = elements.length;
        int[] rotateElements = new int[n*2];
        for(int i = 0; i < elements.length; i++){
			rotateElements[i] = elements[i];
			rotateElements[i+n] = elements[i];
		}
        HashSet<Integer> set = new HashSet<>();
        for(int i = 0; i < n; i++){
			int cnt = 0;
			for(int j = i,jEnd = i+n; j < jEnd; j++){
				cnt += rotateElements[j];
				set.add(cnt);
			}
		}
        return set.size();
    }
}

풀이

• 사용 알고리즘 : 순열
• 원형의 특성을 가진 순열을 구하는 문제다.
  • 예를 들어 1~5의 수, 4부터 4개의 연속 부분수열은 4,5,1,2가 된다.
• 원형의 특성을 간단하게 표현하기 위해서 두개의 elemets를 붙여서 사용하면 된다. 연속 부분수열의 최대 크기는 n개가 되고, 아무리 커도 마지막 인덱스는 (n-1)+n이 된다.