문제:
출처: 프로그래머스 - 연속 부분 수열 합의 개수
문제 설명:
철호는 수열을 가지고 놀기 좋아합니다. 어느 날 철호는 어떤 자연수로 이루어진 원형 수열의 연속하는 부분 수열의 합으로 만들 수 있는 수가 모두 몇 가지인지 알아보고 싶어졌습니다. 원형 수열이란 일반적인 수열에서 처음과 끝이 연결된 형태의 수열을 말합니다. 예를 들어 수열 [7, 9, 1, 1, 4] 로 원형 수열을 만들면 다음과 같습니다.
원형 수열은 처음과 끝이 연결되어 끊기는 부분이 없기 때문에 연속하는 부분 수열도 일반적인 수열보다 많아집니다.
원형 수열의 모든 원소 elements가 순서대로 주어질 때, 원형 수열의 연속 부분 수열 합으로 만들 수 있는 수의 개수를 return 하도록 solution 함수를 완성해주세요.
제한사항:
3 ≤ elements의 길이 ≤ 1,000
1 ≤ elements의 원소 ≤ 1,000
풀이:
기본적으로 시간에 대한 아무런 언급이 없다면 기본은 1초를 기본값으로 잡으면 된다. 그래서 파이썬은 초당 연산 횟수인 1,000만회를 넘기지만 않으면 된다.
길이가 1,000 이기에 2중 반복문 사용이 가능하며, 길이를 2배로 늘려도 연산횟수에는 영향이 없다.
리스트로 주어질 때 문제에서 요구하는 것처럼 연속수열을 만드는 방법은 크게 2가지 정도가 있다.
1. 리스트에 *2를 해서 길이를 늘려주는 것으로, 제일 마지막인 4부터 시작해도 연속수열처럼 합을 연산할 수 있다.
2. 큐 자료구조를 사용하여 7부터 시작하는 합을 모두 구한 후 제일 앞의 것을 빼서 뒤로 보내는 방법이다.
3. 이렇게 구한 합은 중복될 수 있으니 set()자료구조를 이용한 후 set의 길이를 반환하면 된다.
본인이 더 편한 방법을 사용하면 된다.
코드:
- 리스트
def solution(elements):
answer = set(elements)
n = len(elements)
elements = elements * 2 # 연속수열처럼 연산할 수 있도록 길이를 2배 늘려준다.
for i in range(n): # 연속수열의 시작부분
sumN = 0 # 연속수열의 누적합 초기화
for j in range(i, i + n): # 연속수열의 시작부터 마지막부분까지
sumN += elements[j]
answer.add(sumN)# 누적합을 set에 넣어줘서 중복을 제거
# 아래처럼 sum을 할 시 sum의 연산이 일어나서 빅오표기법으로 O(N**3)으로 작동한다.
# answer.add(sum(elements[i:j+1])) # 풀이는 되나 추천하지 않는다.
return len(answer)- 큐
from collections import deque
def solution(elements):
answer = set(elements)
dQ = deque(elements)
for _ in range(len(elements)): 입력값의 길이만큼 반복(제일 앞 부분이 수열의 시작부분)
sumN = 0 # 수열의 합
for _ in range(len(elements)): # 길이만큼 큐에서 빼서 수열의 합을 업데이트
x = dQ.popleft()
sumN += x
answer.add(sumN)
dQ.append(x) # 뺀 수를 제일 뒤로 넣어줌으로써 안쪽 반복문이 모두 끝이나면 다시 제자리로 돌아가 있다.
dQ.append(dQ.popleft()) # 시작 부분을 제일 뒤로 보내서 두 번째가 수열의 첫 번째가 될 수 있도록 한다.
return len(answer)