알고리즘 방식중 투포인터 알고리즘 방식으로 문제를 해결하는방법을 배웠고, 관련 문제와함께 보시죠.
1 . 투포인터 알고리즘이란?
- 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘
- 정렬되어있는 두 리스트의 합집합에도 사용됨. 병합정렬(merge sort)의 counquer 영역의 기초가 되기도 합니다.
자세한 설명은 아래의 블로그를 참조부탁드립니다. 저는 예제와 함께 아래에서 설명을 다시 드리겠습니다.
https://butter-shower.tistory.com/226
2 . 예제
문제는 다음과 같고 자바스크립트로 해결했습니다.
N개의 수로 이루어진 수열이 주어집니다.
이 수열에서 연속부분수열의 합이 특정숫자 M이 되는 경우가 몇 번 있는지 구하는 프로그램을 작성하세요.
만약 N=8, M=6이고 수열이 다음과 같다면
[1,2,1,3,1,1,1,2]
합이 6이 되는 연속부분수열은 {2, 1, 3}, {1, 3, 1, 1}, {3, 1, 1, 1}로 총 3가지입니다.
2 . 1 이중 for문으로 풀기
위는 이중 for문으로 작성해서 첫번쨰 for문은 0번index부터 두번쨰 for문은 1번index부터해서 합이 6보다 작으면 다음 index를 더하고 값이 같다면 answer라는 변수에++ 해주고, 값이 더크다면 2중for문을 break해주면 된다. 그후 첫번쨰 for문을 하나씩 늘리며 이를 배열의 길이만큼 반복한다. 이는 총 시간복잡도 O(n^2)와같다.(투포인터 알고리즘을 적용하기전에 이 방식으로 했다.)
2 . 2 투포인터 알고리즘으로 풀기
이제 이런 수열은 투포인터 알고리즘으로 풀면된다.
function solution(m, arr) {
let answer = 0,
lt = 0,
sum = 0;
for (let rt = 0; rt < arr.length; rt++) {
sum += arr[rt];
if (sum === m) answer++;
while (sum >= m) {
sum -= arr[lt++]; //후치연산이라 값을뺴고 lt를 1증가시킨다.
if (sum === m) answer++;
}
}
return answer;
}
let a = [1, 2, 1, 3, 1, 1, 1, 2];
console.log(solution(6, a));lt값이 첫번째 좌표고 rt값이 두번쨰 좌표가된다.
sum은 값들을 모두 더해서 6인지를 확인하기 위한 변수고 answer는 값이 m과같다면 하나씩 증가시켜서 우리의 정답으로 리턴한다
. 함수에 받는 인자 m은 수열의 합이 몇이여야되는지, arr은 해당 수열이다.
우선 arr[rt]값을 sum에 추가해주고 그즉시 sum과 m값이 같은지 비교해주고 같다면 answer++로 값을 1증가시켜준다.
이제 아래에 while문으로 값이 m과 같거나 클때 lt값만큼 sum에서 뺴준뒤 lt값을 하나 증가시켜준다.
이는 후치연산으로 lt++로 구현했다. 여기서도 sum이 m과 같은지 확인해준뒤 while문을 빠져나온다.
이를 값을 하나씩 넣으며 설명하면 수열a의 첫번쨰 값이 1<6이므로 rt값은 하나증가해 1번index lt값은 그대로 0번index에 머물고, rt값이 1로 바뀌며 1번 index를 더해주면 3<6이므로 한번더 rt값이 하나증가해 2번index로 간다.
이를 3번index까지해주면 총 값은 7>6이 되므로 while문안에 연산이 적용되어 lt의 index가 1번으로 되고 본래 가지고있던값 1을 뺴주며 6=6이돼서 answer를 ++시켜준다.
이제 해당연산이 끝나고 rt값을 1증가하면 7>6이 되므로 while문 안에연산이 적용돼서 5<6이 되므로 while문을 빠져나오고 이과정을 계속 반복하면 {2, 1, 3}, {1, 3, 1, 1}, {3, 1, 1, 1}로 총 answer는 3이나온다.
3 . 투포인터 알고리즘의 시간복잡도
2-1에서 했던 이중for문의 O(n^2)와 다르게 O(n)의 시간복잡도를 갖고있기에 이런 수열의 합과 관련된 문제는 투포인터 알고리즘을 사용하면 시간이 훨씬 단축될 수 있다.
