[홀로 하는 코딩 공부] 연속된 부분 수열의 합(Python)

프로그래머스

사용 언어: Python

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/178870

프로그래머스

*** 본 문제를 푸는 과정을 공유하려 한다.

 

---

▶ 처음에는 아래와 같이 작성해보았다. 

def solution(sequence, k):
    answer = []
    start_idx = 0
    end_idx = len(sequence)
    for idx, value in enumerate(sequence[1:]):
        while True:
            end_idx = (idx+1)
            cur_summation = sum(sequence[start_idx:end_idx+1])
            if cur_summation < k:
                break
            elif cur_summation == k:
                answer.append([start_idx, end_idx-start_idx+1, end_idx])
                break
            else:
                start_idx += 1
    answer.sort(key=lambda x:x[1])
    return [answer[0][0], answer[0][2]]

 

 

▶ 그 결과, 시간초과가 뜬다. 뭐가 문제일지 코드를 다시 보니 sum을 매번 하는 부분에서 시간 초과가 났을 거라고 추정이 되었다. 그래서 매번 인덱스를 이용하여 매번 합 계산을 하지말고 일전 계산을 통해 더한 부분에서 start_idx가 변하면 sequence[start_idx] 값을 빼주고, end_idx가 변하면 sequence[end_idx] 값을 더해주는 방식으로 변경한다. 변경한 코드는 아래와 같다.

def solution(sequence, k):
    answer = []
    start_idx = 0
    cur_summation = sequence[start_idx]

    for end_idx in range(1, len(sequence)):
        cur_summation += sequence[end_idx]
        while True:
            if cur_summation < k:
                break
            elif cur_summation == k:
                answer.append([start_idx, end_idx -start_idx +1, end_idx])
                break
            else:
                cur_summation -= sequence[start_idx]
                start_idx += 1

    answer.sort(key=lambda x :x[1])
    return [answer[0][0], answer[0][2]]

 

▶ 시간초과는 해결하였다. 그런데 33번에서 틀린다. 어떤 반례 때문인지 모르겠어서 구글링을 하였다. Ref_1에서 입력값:[2,2,2,2,2], 2 / 출력값: [0, 0] 와 같은 반례가 있다는 것을 알게 되었다. 위 코드에서는 일단 무조건 for문에서 sequence[end_idx] 값을 cur_summation에 더하게 되어있기에 위 코드에 Ref_1의 입력값을 넣어보면 [1,1]이 출력된다. 그러므로 for문이 돌아가기전에 sequence[start_idx]값 만이 더해진 cur_summation이 k 값과 동일한지부터 검사하고 맞다면 바로 return 되는 코드를 추가한다. 추가한 코드는 아래와 같다.

 

def solution(sequence, k):
    answer = []
    start_idx = 0
    cur_summation = sequence[start_idx]
    if cur_summation == k:
        return [start_idx, start_idx]
    for end_idx in range(1, len(sequence)):
        cur_summation += sequence[end_idx]
        while True:
            if cur_summation < k:
                break
            elif cur_summation == k:
                answer.append([start_idx, end_idx -start_idx +1, end_idx])
                break
            else:
                cur_summation -= sequence[start_idx]
                start_idx += 1

    answer.sort(key=lambda x :x[1])
    return [answer[0][0], answer[0][2]]

 

 

▶ 반례까지 생각하는 부분은 아직도 부족한 것 같다. 

 

 

Ref_1) https://school.programmers.co.kr/questions/49964?referer=collection-of-questions

 

---

>> 위 내용은 필자가 코딩테스트 문제를 푼 코드입니다.

>> 부족한 점이 많을 수 있기에 잘못된 내용이나 궁금한 사항이 있으면 댓글 달아주시기 바랍니다.

>> 긴 글 읽어주셔서 감사합니다.