프로그래머스 Lv2 문제입니다. 실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.

문제

https://school.programmers.co.kr/learn/courses/30/lessons/178870

⌛ 54분

def solution(sequence, k):
    answer = [len(sequence),0,len(sequence)-1]
    front = 0
    rear = 0
    tmp = sum(sequence[front:rear+1])
    len_seq = len(sequence)

    sequence += [0]
    while front<=rear and front>=0 and rear<=len_seq-1:

        if tmp==k:
            length = rear-front+1
            if length < answer[0]:
                answer = [length,front,rear]
            elif length == answer[0] and front<answer[1]:
                answer = [length,front,rear]
            rear += 1
            tmp += sequence[rear]
        elif tmp<k:
            rear += 1
            tmp += sequence[rear]
        else:
            tmp -= sequence[front]
            front += 1

    return answer[1:]

비내림차순(오름차순, 중복O)의 수열(sequence)이 주어질 때, 연속된 구간의 합이 k인 구간 중 길이가 가장 짧으며 시작 인덱스가 가장 앞에 있는 구간을 구하는 문제입니다.🐍🐍🐍

전형적인 투 포인터 알고리즘 문제입니다.

이를 구현하기 위해 시작 인덱스(front)와 끝 인덱스(rear)를 0,0으로 초기화한 뒤, 현재 구간의 합이 작다면 rear를 늘리고 크거나 같다면 front를 늘리는 방식으로 구현하였습니다.

이때 구간의 합이 k를 만족한다면, 구간의 길이와 시작 인덱스를 고려하여 답을 초기화하였습니다.

[다른 사람의 풀이1]

def solution(sequence, k):
    answers = []
    sum = 0
    l = 0
    r = -1
    
    while True:
        if sum < k:
            r += 1
            if r >= len(sequence):
                break
            sum += sequence[r]
        else:
            sum -= sequence[l]
            if l >= len(sequence):
                break
            l += 1
        if sum == k:
            answers.append([l, r])
    
    answers.sort(key=lambda x: (x[1]-x[0], x[0]))
    return answers[0]

'나의 풀이'와 같이 현재 구간의 합이 크다면 끝 인덱스(r)를 늘리고 같거나 작다면(l) 인덱스를 늘린 방식입니다.🐥🐥🐥

이후, lambda식을 통해 구간의 길이/시작 인덱스를 기준으로 정렬하여 답을 도출하였습니다.

[다른 사람의 풀이2]

def solution(sequence, k):
    answer = []
    start, end = 0,0
    temp = sequence[0]
    min_len = 1000001

    while start <= end < len(sequence):
        if temp == k :
            if end - start + 1 < min_len :
                min_len = end - start + 1
                answer = [start, end]
            temp -= sequence[start]
            start += 1

        elif temp < k :
            end += 1
            if end < len(sequence) :
                temp += sequence[end]

        elif temp > k :
            temp -= sequence[start]
            start += 1

    return answer

이외 다른 풀이들도 투 포인터 알고리즘을 활요한 방식이였습니다.

감사합니다.