알고리즘_투포인터

인프런 JS 알고리즘 문제풀이 5-2

N개의 수로 이루어진 수열이 주어집니다.
이 수열에서 연속부분수열의 합이 특정숫자 M이하가 되는 경우가 몇 번 있는지 구하는 프로그 램을 작성하세요.
만약 N=5, M=5이고 수열이 다음과 같다면
1 3 1 2 3
합이 5이하가 되는 연속부분수열은 {1}, {3}, {1}, {2}, {3}, {1, 3}, {3, 1}, {1, 2}, {2, 3}, {1, 3, 1}로 총 10가지입니다.

▣ 입력설명
첫째 줄에 N(1≤N≤100,000), M(1≤M≤100,000,000)이 주어진다. 수열의 원소값은 1,000을 넘지 않는 자연수이다.

▣ 출력설명
첫째 줄에 경우의 수를 출력한다.

▣ 입력예제
5 5
1 3 1 2 3

▣ 출력예제
1 10

풀이

문제를 우선 해석해보자.
연속 부분 수열의 합이 특정숫자 M 이하가 되는 갯수 를 구하는 문제다.
위 그림 처럼 1 3 1 2 3 의 블럭이 있다고 생각하고, 특정 숫자 M=5라면,
{1}, {3}, {1,3}, {3,1}, {1,3,1}, {1}, {1,2}, {2}, {2,3}, {3}
10개가 답이다.
전체 수열중 <= 5 부분의 수열 영역을 투포인터로 다 구하고, 그 영역에서 만들수 있는 부분 수열의 갯수를 카운트 하면 된다.

start 포인트를 left, lt라 하고 end 포인트를 right, rt라 한다면,
이 문제 푸는 간단히 말하면,

1. 일단 sum, lt, rt 변수를 만들고 rt 기준으로 전체 for문을 만들고 lt와 rt 사이 영역을 sum변수에 sum해준다
2. sum<=5라면 사이 영역에 부분 수열로 만들수 있는 모든 수열을 count해서 더해준다.(중복 주의)
3. 그럼 모든 로직 1회전 돌면 rt 기준으로 for문을 만들었으니 for루프가 돌면서 rt+=1이 되고 다시 위에서 말한 로직을 반복해준다. 그런데, rt가 계속 루프 돌면 sum>5되는 순간이 오는데, 그때 lt에 lt++
   해줘서 앞으로 한칸을 움직인다. 그전에 sum에서 기존 lt포인터 값을 제거해준다 sum-= array[lt]. 그래야 lt++했을때 lt와 rt사이 영역의 합이 반영된다.

이제 코드를 만들어보자.

풀이 - 코드

1. 위에 1번을 구현하면 위와 같다. TwoPointer 문제는 깔끔하게 for문은 rt기준으로 만들어주고, sum += array[rt] 부분이 가장 로직 상단에 있어야 한다. 이 것땜에 삽질을 많이 했는데(로직 중간에 sum+= array[rt] 작업이 들어가면 상당히 골치아파진다. sum한 이후 조건을 달아야되고.. 암튼 고려할게 많아지게 된다.) 상식적으로 rt point가 한칸 앞으로 간 후 바로 sum += 해주는게 직관적이다.

2. 모든 수열 count 코드 짤때 주의할 점이 있는데,
   만약 lt=0, rt=0이면 값은 {1}이니 1개이다. rt=1이면 rt point는 3에 가 있을테니 그 사이 수열은 1,3 이고 만들수 있는 모든 수열은 {1},{3},{1,3} 3개지만, 앞의 rt=0일때 {1}이 중복된다. 따라서 2개,
   한번더,
   rt=2이면, rtPoint는 세번째 숫자 1에 위치하고, 사이 수열은 1,3,1 이고, 만들수 있는 모든 수열 중 앞에 나온 중복(={1},{3},{1,3})을 빼고 계산하면, {1},{1,3,1}, {3,1} 3개다.
   rt=3이면, {2}, {1,3,1,2}, {3,1,2}, {1,2} 4개..
   즉 rt와 lt를 사용해 수식을 세우면 rt - lt + 1는 만들수 있는 수열 갯수라는 걸 알 수 있다.

위 코드를 보면 console에 계산 식이 찍혀 나온다.
다만 #55행에 answer는 누적 된 값을 구해야 하니까 아래처럼 +=로 바꿔준다

3. sum>5 일 경우, lt포인터를 움직이는 코드가 빨간 네모 부분이다.
sum과 같거나, 이하가 초과보다 조건이 하나 더 많아지니 초과하는 조건을 만들어 주는게 좋다. 무슨말이냐면, if(sum<=5)이런식으로 조건식을 만들고 로직을 짜나가면 if 바깥 부분은 sum>5 조건 하나만 해당되니, 낭비이면서 더 어려워진다.
5보다 적거나, 같다는 조건이 2개고, 5보다 크다는 조건이 1개니, 조건이 더 적은 쪽으로 분기를 만드는게 좋다.
for문과 관계없이(=rt의 이동과 관계없이) lt를 조건에 따라 이동시켜야 하면서 sum<=5 될때까지 반복해야 하므로 while을 사용한다.

while과 for문 사용 방법은 몇번 도는지 횟수를 알 수 있을땐 for문을 사용하고 몇번 돌지 모를땐 while문을 사용한다.

while문 내에 코드를 보면 lt 이동에 따라 sum 값에서 현재 lt의 값 (=array[lt]) 를 빼주고, lt를 한칸 앞으로 이동시킨다.
arrat[lt++]로 단축시키지 않고 풀어서,

sum -= array[lt];
lt += 1;

로 해줘도 문제없다.
콘솔에 정답인 10이 나온다.
-끝-

실수 요인

1. for문 돌때 가장 처음 로직에 ㄱ. sum += array[rt] 를 해줘야 한다는 것을 이해 못해서 적용 못한것. lt를 start포인터로 두고, rt를 end포인터로 두며,
   전체 for문이 rt를 +1씩 계산되어 돌아간다고 할때, 가장 처음에 할일은 ㄱ. 이다. 우선적으로sum에 +1 rt 인덱스가 적용된 array[rt]를 sum해주고, 그 이후에 다른 조건식이나 로직이 들어가야 된다

2. 합이 5이하인 부분수열의 갯수가 문제니깐, lt와 rt 사이의 배열 요소로 만들수 있는 전체 부분수열 갯수를 카운트 하면된다. 그걸 카운트 하는 식이 answer = rt - lt + 1 이고 (야 이걸 어떻게 찾아내냐. 수열 보고 반복되는 규칙 찾는건데.. 진짜 미친거 아닌가 ㅋㅋㅋ)
   이 answer계산식을 for 루프 돌면서 answer += rt - lt +1 로 계속 재 대입 해주면 됨. 카운트 하는 식을 못 떠올린 것.(당연히 못 떠올리지..ㅠ) 정확히는 부분수열로 만들어 수 있는 수열 전체 갯수가 답이란걸 이해 못한점.