연속 부분 수열 합의 개수

• 문제 설명
  • 철호는 수열을 가지고 놀기 좋아합니다. 어느 날 철호는 어떤 자연수로 이루어진 원형 수열의 연속하는 부분 수열의 합으로 만들 수 있는 수가 모두 몇 가지인지 알아보고 싶어졌습니다. 원형 수열이란 일반적인 수열에서 처음과 끝이 연결된 형태의 수열을 말합니다. 예를 들어 수열 [7, 9, 1, 1, 4] 로 원형 수열을 만들면 다음과 같습니다.
    

    

  • 원형 수열은 처음과 끝이 연결되어 끊기는 부분이 없기 때문에 연속하는 부분 수열도 일반적인 수열보다 많아집니다.
  • 원형 수열의 모든 원소 elements가 순서대로 주어질 때, 원형 수열의 연속 부분 수열 합으로 만들 수 있는 수의 개수를 return 하도록 solution 함수를 완성해주세요.
• 제한 조건
  • 3 ≤ elements의 길이 ≤ 1,000
  • 1 ≤ elements의 원소 ≤ 1,000
• 입출력 예

 

 

• 실패코드
  • 딕셔너리를 이용하여 중복 제거
  • 반복문의 다중 사용으로 인한 시간복잡도가 증가하는 문제로 해당 코드로 제출시 런타임 에러 발생

def solution(elements):
    answer = 0
    num_dict = {}
    
    for i,num in enumerate(elements):
        num_dict[num] = 1
        k = i
        for j in range(len(elements)):
            k = k % len(elements)
            name = elements[k]
            for s in range(1,i+1):
                name += elements[(k+s) % len(elements)]
            num_dict[name] = 1
            k += 1
            
    answer = len(num_dict)
    return answer

 

• 수정코드
  • 기존에 나머지 구하는 부분을 그냥 elements를 그대로 복사하여 [1,2,3,4]가 있으면 나머지 계산으로 각각 자리를 구하는게 아닌 [1,2,3,4,1,2,3,4]를 통하여 나머지 계산 없이 바로 자릿 수만큼 배열을 가져오도록 수정
  • 3중 반복문을 2중 반복문으로 수정

def solution(elements):
    answer = 0
    num_dict = {}
    lens = len(elements)
    long_elements = elements + elements[:-1]
    for i,num in enumerate(elements):
        sums = num
        num_dict[sums] = 1
        for j in long_elements[i+1:i+lens]:
            sums += j
            num_dict[sums] = 1
            
    answer = len(num_dict)
    return answer