-
프로그래머스_연속된 부분 수열의 합(python)Algorithm/프로그래머스_생각정리 2023. 4. 10. 15:00
※ 접근
sequence의 길이가 최대 백만이었기에 중첩 포문을 돌면 안되겠다는 생각이 제일 먼저 떠올랐다. 구간 합을 구하고 그 구간이 계속 변해가야하기에 left,right 투 포인터를 사용하기로 했다.
※ 풀이
1. 첫 시작과 나중을 구분했다. 그 이유는 처음에는 k를 같든 작든 크든 right가 오른쪽으로 이동해줘야 하기 때문이다.
(right는 left보다 같거나 큰 idx에 위치해야 하기 때문이다. )
2. temp == k라면 구간의 길이를 key로 하고 left, right를 사전형에 추가시켜준다. left와 right를 오른쪽으로 한 칸씩 이동시켜준다.
3. temp > k라면 left를 줄여준다.
4. temp < k라면 right를 한 칸 오른쪽으로 이동시켜준다.
5. 마지막에 가장 작은 key를 찾아 첫 인덱스 별로 정렬 시켜주고 0번 인덱스를 answer에 넣어주면된다.
from collections import defaultdict def solution(sequence, k): s = defaultdict(list) temp = 0 left, right = 0, 0 temp, i = 0, 0 while right < len(sequence) and left < len(sequence): if i == 0: temp = sequence[0] if temp == k: s[right+1-left].append([left,right]) right += 1 # 처음에는 일단 right가 넘어가는게 맞음 if not right < len(sequence): break temp += sequence[right] i += 1 else: if temp == k: s[right+1-left].append([left,right]) temp -= sequence[left] left += 1 right += 1 if not right < len(sequence): break temp += sequence[right] elif temp > k: temp -= sequence[left] left += 1 else: right += 1 if not right < len(sequence): break temp += sequence[right] min_len = min(s.keys()) min_list = s[min_len] min_list = sorted(min_list, key=lambda x:x[0]) answer = min_list[0] return answer
※ 회고
화이팅!!!
'Algorithm > 프로그래머스_생각정리' 카테고리의 다른 글
프로그래머스_level2_디펜스 게임 (python) (0) 2023.07.27 프로그래머스_과제 진행하기(python) (0) 2023.04.02 프로그래머스_광물캐기_level2(python) (0) 2023.03.26 프로그래머스_두 큐 합 같게 만들기_level2(python) (0) 2023.03.23 프로그래머스_level 2_리코쳇 로봇(python) (0) 2023.03.19