문제
문제 : https://school.programmers.co.kr/learn/courses/30/lessons/131701
수열을 갖고 놀기 좋아하는 철호는 어떤 자연수로 이루어진 원형 수열의 연속하는 부분 수열의 합으로 만들 수 있는 수가 모두 몇 가지인지 알고 싶어졌다.
원형 수열이란 일반적인 수열에서 처음과 끝이 연결된 형태의 수열을 말한다. 예를 들어 수열 [7, 9, 1, 1, 4]로 원형 수열을 만들면 다음과 같다.
원형 수열은 처음과 끝이 연결되어있어 연속하는 부분 수열도 일반 수열보다 많다. 원형 수열의 원소 elements가 주어질 때, 원형 수열의 연속 부분 수열의 합으로 만들 수 있는 수의 개수를 반환하라.
풀이 1
프로그래밍적으로 원형 수열을 다룰 때는 인덱스를 리스트 길이로 나눈 나머지로 취급하게 된다. 다만, 꼼수로 리스트를 두 번 반복하면 나머지 계산 없이 원형 수열처럼 다를 수 있다.
아래는 수열을 두 번 반복하여, 1부터 수열의 길이만큼의 부분 수열을 슬라이싱한 뒤 그 합을 구한다.
def solution(elements):
answer = set()
elements += elements
for l in range(1, len(elements)//2 + 1):
for s in range(len(elements)//2):
answer.add(sum(elements[s:s + l]))
return len(answer)
풀이 2
아래 풀이는 나머지 계산을 통해 원형 수열을 취급한 것이다. 다만 부분 수열 원소의 합을 구하므로, 부분 수열을 슬라이싱하는 대신 그 합을 계속 추가해 주었다.
def solution(elements):
answer = set()
len_elements = len(elements)
for i in range(len_elements):
s = 0
for j in range(len_elements):
s += elements[(i+j) % len_elements]
answer.add(s)
return len(answer)
참고 문서