[Programmers] 연속된 부분 수열의 합

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

프로그래머스

 

투 포인터 알고리즘으로 푼 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. start와 end는 부분 수열의 시작과 끝을 가리키는 인덱스 값을 저장하는 변수이며 [0, 0] 범위부터 시작합니다.

2. 현재 부분 수열의 합이 k보다 작을 경우 범위를 더 넓혀야 하므로 end를 1 증가시킵니다.

2.1. 현재 부분 수열의 합이 k와 같다면 문제 조건에 따라 두 가지 케이스로 구분해서 봐야 합니다.

2.1.1 합이 k인 부분수열이 여러 개인 경우 길이가 짧은 수열을 찾아야 하므로 조건을 만족하는 부분 수열 중 현재 부분 수열의 길이가 가장 짧다면 범위를 현재 범위로 업데이트합니다.

2.1.2 길이가 같을 경우 시작 인덱스가 작은 수열이 답이므로 현재 부분 수열의 시작 인덱스가 더 작을 경우 현재 범위로 업데이트합니다.

2.2 합이 k 이상일 경우 시작 인덱스를 1 증가시켜 범위를 좁히며 더 최적의 답을 찾습니다.

3. 2번의 과정을 반복하여 최적의 답을 찾아 반환합니다.

 

\

 

개발환경: Programmers IDE

지적, 조언, 질문 환영합니다! 질문 남겨주세요~