Two Pointers Algorithm
- list의 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 Algorithm
- 정렬되어있는 두 개의 list의 합집합에도 사용된다. merge sort의 conquer 영역에서 기초가 된다.
즉 정렬된 list를 두 개의 포인터를 이용해서 순차적으로 접근하면서 두 포인터 구간의 값이 target 값과 같을 때까지
포인터를 조작하는 것이다.
두 개의 포인터를 활용하면 list를 한 번만 탐색하므로 list가 이미 정렬되어져 있는 경우 O(n), 정렬되어 있지 않아도 O(nlogn) 정도 time complexity로 문제를 해결 할 수 있다. 그러므로 주어진 입력 데이터가 클 경우에는 투 포인터를 활용할 수 있는지를 꼭 생각해보자.
arr1의 p1과 arr2의 p2라는 배열에서 누가 더 작냐 비교해서 작은 것을 answer에 push하면 된다.
push된 쪽의(p1이나 p2) 포인터는 한칸 증가해서 다시 비교를 진행한다.
한 쪽 배열이 다 탐색이 되면 남은 지역쪽의 것 들을 쭉 집어넣는다.
아래코드를 참고하자.
<html>
<head>
<meta charset="UTF-8">
<title>출력결과</title>
</head>
<body>
<script>
function solution(arr1, arr2) {
let answer = [];
let n = arr1.length;
let m = arr2.length;
let p1 = p2 = 0;
while (p1 < n && p2 < m) {
if (arr1[p1] <= arr2[p2]) answer.push(arr1[p1++]);
else answer.push(arr2[p2++]);
}// arr1이 남았다 or arr2가 남았다면
while (p1 < n) answer.push(arr1[p1++]);
while (p2 < m) answer.push(arr2[p2++]);
return answer;
}
let a = [1, 3, 5];
let b = [2, 3, 6, 7, 9];
console.log(solution(a, b));
</script>
</body>
</html>
<출처 : 자바스크립트 알고리즘 문제풀이(코딩테스트 대비): 김태원>
자바스크립트 알고리즘 문제풀이(코딩테스트 대비) - 인프런 | 강의
자바스크립트(JavaScript)로 코딩테스트를 준비하시는 분을 위한 강좌입니다. 재미있게 풀 수 있는 기초 단계 문제부터 고급 알고리즘까지 단계별로 차근차근 배우도록 설계된 강좌입니다., 개발
www.inflearn.com
https://butter-shower.tistory.com/226
[Algorithm] 투포인터(Two Pointer) 알고리즘
알고리즘 문제를 풀다보면 종종 나오는 투포인터 알고리즘! 막 꼬여가지고 ㅋㅋㅋ 저도 중간에 제대로 못짜고 그러는 경우가 많은데요, 많은 코딩테스트 문제에 등장하는 것은 아니지만 잊을만
butter-shower.tistory.com
https://velog.io/@adorno10/%ED%88%AC-%ED%8F%AC%EC%9D%B8%ED%84%B0-Two-Pointer
투 포인터 (Two Pointer)
정렬된 리스트를 두 개의 포인터를 이용해 순차적으로 접근하면서 두 포인터 구간의 값이 타겟 값과 같을 때 까지 포인터를 조작하는 기법을 말한다. 두 개의 포인터를 함께 활용할 때 얻을 수
velog.io
'JavaScript > JS_Algorithm' 카테고리의 다른 글
| [인프런 - JS 알고리즘 문제풀이] stack판단3 (0) | 2021.08.05 |
|---|---|
| [인프런 - JS 알고리즘 문제풀이] stack판단2 (0) | 2021.08.05 |
| [인프런 - JS 알고리즘 문제풀이] stack판단 (0) | 2021.08.05 |
| [인프런 - JS 알고리즘 문제풀이] 공통인자 구해보기 (0) | 2021.08.05 |
| [인프런 - JS 알고리즘 문제풀이]아나그램 갯수문제(Hashing과 연관) (0) | 2021.08.05 |