투포인터를 이용한 부분합 문제이다. 이전에 비슷한 유형을 풀이했었는데, 시간이 지나니까 생각이 나지 않았고 그냥 흐릿하게 이건 투포인터로 푸는 것 같다 라는 느낌이 들었다.
그래서 투포인터 부분합을 그대로 갔다가 사용했는데 합격이 나왔다.
암튼 TMI였다.
1. 문제 설명
Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개라는 사실을 알게 되었습니다. 예를들어 15는 다음과 같이 4가지로 표현 할 수 있습니다.
1 + 2 + 3 + 4 + 5 = 15
4 + 5 + 6 = 15
7 + 8 = 15
15 = 15
자연수 n이 매개변수로 주어질 때, 연속된 자연수들로 n을 표현하는 방법의 수를 return하는 solution를 완성해주세요.
2. 어려웠던 점
문제를 읽으면서 투포인터로 푸는거 같았는데 왜 인지에 대해 설명을 못했다.
정리해보니 그냥 투포인터 구간합이 말 그대로 2개의 포인터로 연속된 구간 합을 구하는
것이었다. 왜 고민을 했을까 안해도 되는데..
2-1. 투포인터 구간합의 개념
1) 주로 언제 쓰이는가?
수열에서 특정한 합을 가지는 부분 연속 수열의 합을 구할때
2) 어떻게 구현하는가?
찾고자 하는 부분 연속 수열의 합을 M이라고 하자.
부분 연속 수열의 개수(count)를 가리키는 변수를 만든다.
시작점(start)과 끝점(end)를 가리키는 변수를 만든다.
(현재 부분 합 == M) --> count += 1
(현재 부분 합 <= M) --> end += 1
(현재 부분 합 > M) --> start += 1
3. 풀이 아이디어
부분합을 그대로 사용했다.
현재의 부분합이 동일하면, 카운트를 증가시키고 왼쪽에 있는 포인터를 이동한다.
그리고 부분합이 목표보다 작게 되면 카운트를 증가시키고 앞쪽으로 전진 + 오른쪽의 포인터를 한칸 앞으로 이동시킨다.
부분합이 크면 줄인다.
그리고 오른쪽의 포인터가 리스트의 맨 끝까지 왔다면 오른쪽 포인터의 이동은 중단하고, 왼쪽 포인터만 이동시킨다.
3-1. 풀이
def solution(n):
# 먼저 1부터 더해서 15가 되는 범위를 파악하기
# 투포인터로 간다!!!!!!!!
a = [i for i in range(1,n+1)]
target = n
left, right = 0,0
cnt = 0
tot = 0
while left < len(a):
if tot == target: # 합이 같으면
cnt += 1 # cnt를 증가시키고
tot -= a[left] # 토탈합에서 가장 아래쪽에 있는 포인터를 빼고
left += 1 # 그 다음으로 이동
elif tot > target or right >= len(a):
tot -= a[left]
left += 1
elif tot < target:
tot += a[right]
right += 1
return cnt