프로그래머스_연속된 부분 수열의 합_Day5

알고리즘 챌린지 5일 차이다. 오늘은 정말 아슬아슬했다. 한 잔 하러 나갔다가 마음을 돌려 집에 와서 알고리즘을 풀었다. 

오늘도 마찬가지로 프로그래머스 Level 2 에 분류된 문제이다. 문제가 익숙한 듯 어려운 듯 쉽지만 슬라이딩 윈도 기법을 알고 있다면 생각보다 쉽게 풀이할 수 있다. 

https://school.programmers.co.kr/learn/courses/30/lessons/178870?language=python3

프로그래머스

부분 수열을 나타낼 시작과 끝 포인터를 논리적으로 만들어준다. 포인터를 하나씩 이동하면서 두 포인터 사이의 있는 값들의 합과 문제에서 주어지는 k를 비교하여 때에 따른 적절한 대처를 해주면 된다. 

1. 부분 합 == k인 경우 

문제에서 원하는 답을 찾았다...! 생각하고 답을 제출해버리면 안 된다. ㅋㅋ 조건에 만족하는 부분 수열이 한 가지가 아닐 수도 있기 때문이다. 여러 가지 일 수도 있고, 그중 가장 짧으면서 길이가 같은 것 중에서는 인덱스가 작은 부분 수열을 리턴해야 한다. 

따라서 조건을 만족하는 경우 일단 최소 길이 값과 비교하여 그 값보다 작은 경우만 answer값을 갱신해준다. 

이때, 최소 길이 값보다 작은 경우만 갱신하는 이유는 앞에서 나온 부분 수열의 길이가 2인데, 조건을 만족하고, 뒤에서 나온 길이도 2로 만족한다면 뒤에서 나온 값은 최소 값 2보다 작지 않기 때문에 값이 갱신되지 않는다. 반대로 뒤에서 나온 부분 수열의 길이가 전자보다 작다면, 더 짧은 것이 우선적인 조건이기 때문에 값을 갱신하더라도 문제를 벗어나지 않는다. 

값을 갱신한 후에는 그 뒤에 다른 경우의 수를 찾기 위해서 부분합에서 start의 값을 빼주고 start의 위치를 뒤로 한 칸 이동한다.

2. 부분 합 < k 

k값에 근접하기 위해서 값을 하나 더 더해준다. end 포인터를 뒤로 한 칸 이동시키면 된다. 
이때 여기서 제약 조건은 end 값이 sequence 배열의 길이보다 커지면 IndexOutOfBoundsException이 발생할 수 있기 때문에, end 값이 배열의 길이보다 작은 경우에만 리스트에 접근하여 부분합을 추가해 준다. 

3. 부분 합 > k

k값에 근접하기 위해서는 부분 수열의 원소를 하나 제외해야 하기 때문에 start값을 빼고 start의 인덱스를 하나 뒤로 이동시켜준다. 

슬라이딩 윈도우 기법에 대한 간단한 느낌이 오는가? 
start를 이동시키면서 부분 수열의 원소를 줄이고, end를 이동시키면서 부분 수열의 원소를 늘린다. 이러한 움직임 속에서 조건에 만족하는 경우의 수를 체크해 주는 것이다. 
이러한 모습이 창문이 움직이는 모습과 비슷하다하여 붙여진 이름이라고 한다. 

코드로 살펴보자. 

Python

def solution(sequence, k):
    answer = []
    start, end = 0, 0
    partialHap = sequence[0] 
    minLen = 1000001
    
    while start <= end < len(sequence) :
        if(partialHap == k):
            #최소 길이를 구하기 위한 로직
            if(end-start+1 < minLen):
                minLen = end-start+1
                answer = [start, end]
            partialHap -= sequence[start]
            start += 1
            
        elif partialHap < k :
            end += 1
            if end < len(sequence):
                partialHap += sequence[end]
        elif partialHap > k:
            partialHap -= sequence[start]
            start += 1
    return answer