요즘 코딩테스트에 자주 등장하는 투 포인터 알고리즘!!
저도 대세에 따라가기 위해 투 포인터를 다시 되짚어봤습니다~
투 포인터(Two Pointer) 알고리즘에 대해 공부하고, js를 이용해 관련 문제까지 풀어봤습니다😊
1. 투 포인터 (Two Pointer) 알고리즘
투 포인터 알고리즘은 리스트에 순차적으로 접근해야 할 때, 2개의 포인터로 위치를 기록하며 처리하는 알고리즘입니다.
리스트 속 데이터에 순차적으로 접근해야 할 때는 시작점 & 끝점 2개의 포인터로 데이터의 범위를 설정할 수 있습니다.
예시로 '2, 3, 4, 5, 6, 7번 학생'은 ‘2번부터 7번까지 학생’과 마찬가지의 의미를 가집니다. 이렇게 시작점(2번)과 끝점(7번)으로 범위를 나타냅니다.
투 포인터 알고리즘을 사용하면 그냥 탐색(반복문, 이중 for문)을 사용할 때보다 메모리 효율 & 시간 효율을 높일 수 있습니다.
2. 자바스크립트를 이용한 투 포인터 알고리즘 관련 문제 풀이
2-1. 🔍 특정한 합을 가지는 부분 연속 수열 찾기
❓ 문제 설명
N개의 자연수로 구성된 수열이 있을 때, 합이 M인 부분 연속 수열의 개수를 구하시오.
이 때의 N = 5, M = 5이다.
📖 풀이 코드
let n = 5; //데이터 개수 N
let m = 5; //찾고자 하는 부분합 M
let data = [1, 2, 3, 2, 5]; //전체 수열
let count = 0;
let sum = 0;
let end = 0;
for (let start = 0; start < n; start++) { //start를 차례대로 증가시키며 반복
while (sum < m && end < n) { //end를 가능한 만큼 이동
sum += data[end];
end++;
}
if (sum == m) count++; //부분합이 m이면 count 증가
sum -= data[start]; //while문을 탈출한 경우 ➡️ start 증가
}
console.log("count =", count); //count 출력
📢 풀이 설명
이 문제는 항상 start가 증가하면 합이 감소, end가 증가하면 합이 증가하기 때문에 투 포인터 알고리즘을 사용할 수 있다. 즉, 음수 값이 포함되어 있으면 투포인터 알고리즘 사용 불가하는 뜻이다.
- 시작점(start)과 끝점(end)이 data의 첫 번째 원소인 인덱스(0)를 가리키도록 한다.
- 현재 부분 합이 M과 같다면, count를 +1 한다.
- 현재 부분 합이 M보다 작다면, end를 1 증가시킨다. 이때 부분합이 증가한다.
- 현재 부분 합이 M보다 크거나 같다면, start를 1 증가시킨다. 이때 부분합은 감소한다.
- 모든 경우를 확인할 때까지 위의 과정을 반복한다.
2-2. 🔍 정렬되어 있는 두 리스트의 합집합
❓ 문제 설명
오름차순으로 정렬된 두 배열이 있을 때, 두 배열을 합쳐 오름차순으로 나열하시오.
이때의 배열은 a = [1, 3, 5], b = [2, 4, 6, 8]이다.
📖 풀이 코드
let a = [1, 3, 5];
let b = [2, 4, 6, 8];
let n = 3, m = 4; //배열 a와 b 크기
let result = []; //결과를 담을 빈 배열 (리스트)
let i = 0, j = 0, k = 0; //인덱스 값 초기화
while (i < n || j < m) { //모든 원소가 리스트에 담길 때까지 반복
if (j >= m || (i < n && a[i] <= b[j])) { //b의 모든 원소가 처리되거나 / a의 원소가 더 작을 때
result[k] = a[i]; //해당 a 원소 리스트로 옮김
i++;
} else { //a의 원소가 모두 처리되거나 / b의 원소가 더 작을 때
result[k] = b[j]; //해당 b 원소 리스트로 옮김
j++;
}
k++; //리스트 배열 인덱스 증가
}
console.log("result =", result); //결과 리스트 출력📢 풀이 설명
1. 정렬 되어있는 리스트 a, b를 입력받고, 결과를 담을 빈 배열 result를 만든다.
2. 리스트 a에서 처리되지 않은 원소 중 가장 작은 원소를 i가 가리키도록 한다. if-else문을 사용한다.
3. 리스트 b에서 처리되지 않은 원소 중 가장 작은 원소는 j가 가리키도록 한다.
4. a[i]와 b[j] 중에서 더 작은 원소를 result[k]에 담는다.
5. 리스트 a, b에서 더이상 처리할 원소가 없을 때까지 위의 과정을 반복한다. 이때 while문을 이용한다.
참고한 자료: 이것이 취업을 위한 코딩 테스트다 with 파이썬 (저자 나동빈)
