#실패코드
def solution(elements):
    answer = set()
    n = len(elements)
    for i in range(n) : #부분집합크기
        for j in range(n) : #배열 순환
            temp = 0
            for k in range(i) : #크기만큼 돌면서 더함
                temp += elements[(j + k)%n]
            answer.add(temp)
    return len(answer)

from collections import deque

def solution(elements):
    temp = deque(elements)
    answer = elements[:]
    n = len(elements)
    for i in range(1, n) : 
        temp.append(temp.popleft())
        for j in range(n) :
            temp[j] += elements[j]
        answer += temp
    return len(set(answer))

• 문제정리

  원형으로된 배열이 존재할때

  

  해당 원형수열의 부분집합을 구하여 부분집합의 합들을 구해 return하는 문제

• 풀이과정

  맨처음에는 직접 모든 경우의 수를 다 더해가며 풀어갔다. 즉 부분집합이 1개일때 2개일때 n개일때까지 모든 경우의 수를 더하여 풀이하였다.

  하지만 시간초과가 발생하여 풀이하지 못하였다.

  이미 작성기전에도 작성하면서 시간초과가 발생할 것을 알았지만 혹시나 하는 마음에 해보았다.

  어떻게든 최적화할 방법을 찾아야했다.

  위에서 모든 경우의 수를 생각해보니 dp와 같이 이전의 부분집합을 계산했던것을 이용하면 최적화 할 수 있을 것으로 생각하였다. 즉 2개로 되어있는 부분집합에 다음숫자를 더해주면 3개인 부분집합의 합을 바로 구할 수 있었다.

  어떻게 더한것을 유지할지 고민이였는데 위의 그림을 보니 아이디어가 나왔다.

  위의 원형수열을 한칸씩 오른쪽으로 돌리고 원래 원형수열과 같은 위치에 있는 값끼리 더해준다면 n+1부분집합의 원소들을 구할 수 있을것같았다. 즉 계속반복하여 원형수열의 n번까지 반복한다면 학 횟수마다 부분집합들을 구할 수 있었다.

  어떻게 원형 수열을 돌리지 고민이였는데 한칸씩 움직여주며 돌리면서 원래의 원형수열과 더하는 과정을 할까하였는데 out of index가 발생할꺼같아서 고민 중이였다.

  고민중 deque를 사용하여 처음것을 빼서 마지막으로 보내주면 한칸씩 옮기는 아이디어를 생각해내어 deque를 이용하여 풀이하였다.

• 풀이 후

  다른 풀이를 보니 부분집합 길이별로 잘라서 모으는게 아니라, 하나를 잡고 거기서부터 모든 길이를 다 자르는 코드가 있었다.