[Programmers] 연속 부분 수열 합의 개수 (Python) (feat.ChatGPT)

코딩 1일 1문제! 오늘의 문제는 프로그래머스의 연속 부분 수열 합의 개수 입니다.

프로그래머스

👨🏻‍💻 문제 풀이 - SOMJANG

1. 

👨🏻‍💻 코드 ( Solution ) - SOMJANG

def solution(elements):
    answer_list = set(elements)
    
    for n in range(1, len(elements) + 1):
        for idx in range(len(elements)):
            if idx+n < len(elements):
                answer_list.add(sum(elements[idx:idx+n]))
            else:
                answer_list.add(sum(elements[idx:]) + sum(elements[:idx+n-len(elements)]))
    
    return len(answer_list)

👨🏻‍💻 ChatGPT 부탁해!

👨🏻‍💻 SOMJANG

당신은 Python3 언어로 프로그래밍을 할 수 있는 개발자 입니다.

문제가 주어지면 문제의 맥락을 파악하고 파악한 내용을 Python3 언어를 사용하여 코드로 작성합니다.

문제를 풀때는 코드의 성능을 고려하여 풀어주세요.

작성한 코드에서 설명이 필요한 부분에는 주석을 달아 설명해줍니다.

제한사항과 입출력예시를 잘 확인하고 풀어주세요.

Python3 로 작성한 코드를 부탁드립니다.

이제 문제를 드리겠습니다.

 

연속 부분 수열 합의 개수

문제 설명

철호는 수열을 가지고 놀기 좋아합니다.

어느 날 철호는 어떤 자연수로 이루어진 원형 수열의 연속하는 부분 수열의 합으로 만들 수 있는 수가 모두 몇 가지인지 알아보고 싶어졌습니다. 원형 수열이란 일반적인 수열에서 처음과 끝이 연결된 형태의 수열을 말합니다.

예를 들어 수열 [7, 9, 1, 1, 4] 로 원형 수열을 만들면 다음과 같습니다.

원형 수열은 처음과 끝이 연결되어 끊기는 부분이 없기 때문에 연속하는 부분 수열도 일반적인 수열보다 많아집니다.

원형 수열의 모든 원소 elements가 순서대로 주어질 때, 원형 수열의 연속 부분 수열 합으로 만들 수 있는 수의 개수를 return 하도록 solution 함수를 완성해주세요.

 

제한사항

3 ≤ elements의 길이 ≤ 1,000

1 ≤ elements의 원소 ≤ 1,000

 

입출력 예

elements result

[7,9,1,1,4] 18

 

입출력 예 설명

 

입출력 예 #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]

💻 ChatGPT - 실패! ( 시간초과! )

해결방법:

이 문제는 수열에서 원형 수열을 만들어 그 중 연속하는 부분 수열의 합으로 만들 수 있는 수의 개수를 구하는 문제입니다.

원형 수열을 만들기 위해 리스트를 두 번 반복하여 연결한 후, 각각의 길이에서 시작하는 부분 수열의 합을 구합니다. 그러나 이렇게 하면 중복된 값이 나오기 때문에, 중복을 제거한 뒤 총 개수를 반환합니다.

이를 위해 set 자료형을 사용합니다.

코드는 아래와 같습니다.

def solution(elements):
    n = len(elements)
    elements = elements + elements  # 리스트를 두 번 반복하여 연결

    sums = set()  # 중복을 제거하기 위해 set 자료형을 사용
    for i in range(n):
        for j in range(i, i + n):
            for k in range(i, j + 1):
                sums.add(sum(elements[k:j+1]))  # 부분 수열의 합을 추가

    return len(sums)  # 중복을 제거한 합의 개수를 반환

시간 복잡도:

코드에서 3개의 반복문이 사용되기 때문에, 이 코드의 시간 복잡도는 O(n^3)입니다. 하지만 제한사항에서 주어진 elements의 길이가 최대 1,000 이하이므로, 이 코드는 충분히 빠르게 동작할 것입니다.

이후 계속 다시 풀어달라고 해보았으나.....

아래와 같이 계속 작성한 코드는 아래와 같습니다... 라면서 코드는 알려주지 않고 계속 설명만.... 하여...

포기하였습니다...

읽어주셔서 감사합니다.

GitHub - SOMJANG/CODINGTEST_PRACTICE: 1일 1문제 since 2020.02.07