[4코1파] 4명의 안드로이드 개발자와 1명의 파이썬 개발자의 코딩 테스트 서막 : 4코1파
Rule :
하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
START :
[3코1파] 2023.01.04~ (47일차)
[4코1파] 2023.01.13~ (38일차)
Today :
2023.02.19 [47일차]
프로그래머스 LV2
연속 부분 수열 합의 개수
https://school.programmers.co.kr/learn/courses/30/lessons/131701
문제 설명
철호는 수열을 가지고 놀기 좋아합니다. 어느 날 철호는 어떤 자연수로 이루어진 원형 수열의 연속하는 부분 수열의 합으로 만들 수 있는 수가 모두 몇 가지인지 알아보고 싶어졌습니다. 원형 수열이란 일반적인 수열에서 처음과 끝이 연결된 형태의 수열을 말합니다. 예를 들어 수열 [7, 9, 1, 1, 4] 로 원형 수열을 만들면 다음과 같습니다.
원형 수열은 처음과 끝이 연결되어 끊기는 부분이 없기 때문에 연속하는 부분 수열도 일반적인 수열보다 많아집니다.
원형 수열의 모든 원소 elements가 순서대로 주어질 때, 원형 수열의 연속 부분 수열 합으로 만들 수 있는 수의 개수를 return 하도록 solution 함수를 완성해주세요.
제한사항
3 ≤ elements의 길이 ≤ 1,000
1 ≤ elements의 원소 ≤ 1,000입출력 예
입출력 예 설명
입출력 예 #1
길이가 1인 연속 부분 수열로부터 [1, 4, 7, 9] 네 가지의 합이 나올 수 있습니다.
길이가 2인 연속 부분 수열로부터 [2, 5, 10, 11, 16] 다섯 가지의 합이 나올 수 있습니다.
길이가 3인 연속 부분 수열로부터 [6, 11, 12, 17, 20] 다섯 가지의 합이 나올 수 있습니다.
길이가 4인 연속 부분 수열로부터 [13, 15, 18, 21] 네 가지의 합이 나올 수 있습니다.
길이가 5인 연속 부분 수열로부터 [22] 한 가지의 합이 나올 수 있습니다.
이들 중 중복되는 값을 제외하면 다음과 같은 18가지의 수들을 얻습니다.
[1, 2, 4, 5, 6, 7, 9, 10, 11, 12, 13, 15, 16, 17, 18, 20, 21, 22]
문제 풀이 방법
elements의 첫번째 원소부터 길이 n개씩 추가해준다
각 원소에서 n을 더해줘서 배열의 인덱스값이 길이가 넘어 가면
아래 코드처럼 인덱싱 해가면서 풀기
약간 시간 초가 오래걸린걸 보면
썩 효율성이 좋은 코드는 아닌 것 같다
증빙
내 코드
def solution(elements):
result = set()
n = 0
while n != len(elements):
n += 1
for i in range(len(elements)):
if i+n > len(elements):
result.add(sum(elements[i:]+elements[:i+n-len(elements)]))
else:
result.add(sum(elements[i:i+n]))
return len(result)증빙
다른 사람 풀이
mod를 사용해서 시간 효율성을 잡은 코드
여담
철호야 이런걸 왜 가지고 놀기 좋아하는지?
다른 걸 가지고 놀 생각은 없는지?
