패스트캠퍼스 JavaScript 코딩테스트 강의 4주차

문종후·2023년 5월 12일

fastcampus 자바 자바스크립트 코딩교육 코딩자격증 코딩테스트 파이썬 패스트캠퍼스 패스트캠퍼스후기 패캠

학습기록

투포인터 알고리즘

간단하게 리스트에 순차적으로 접근할떄 두개의점위치를 기록하면서 처리하는 알고리즘이라고보면됨.
==>그러면 왜쓰고 언제쓰냐?
왜?:복잡도를 줄여줄수있다.
언제?:2개의 리스트의합,배열이나 문자열같은 선형구조에서 2개의포인터를 조절할떄

간단한 예제를 보도록하겠다.

어떤 특정배열이 나열되있는데 (숫자를 요소로가진)
이녀석들의 구간의 합이 0이되는 쌍을 찾는 함수를 만든다고 가정해보자.

이런식으로 이중반복문을 활용해서 풀수가있습니다.

그런데 이문제는 어떻게보면 두개의 포인트를 찾아 기록하면 정답이나온다.(구간 처음시작,마지막)
그러면 투포인터 알고리즘을 활용할수있는 아주좋은예제가되는데

const arr = [-4, -3, -2, -1, 0, 1, 2, 5];
//left(-4) right(5) ---- 1
const arr = [-4, -3, -2, -1, 0, 1, 2, 5];
//left(-4) right(2) ---- -2
const arr = [-4, -3, -2, -1, 0, 1, 2, 5];
//left(-3) right(2) ---- -1
const arr = [-4, -3, -2, -1, 0, 1, 2, 5];
//left(-2) right(2) ---- 0 [-2, 2] 출력

-4와 5를 더하면 1 --> 양수 (더해서 0이 되는 쌍을 찾아야하기 때문에 right를 작은쪽으로 한칸 옮긴다.)
-4와 2를 더하면 -2 --> 음수 (작은값 포인터 left를 큰쪽으로 한칸 옮긴다.)
-3과 2를 더하면 -1 --> 음수 (작은값 포인터 left를 큰쪽으로 한칸 옮긴다.)
-2와 2를 더하면 0 --> 쌍을 찾았으므로 출력한다.
(이문제는 어떻게보면 오름차순으로 배열이 구성되어있기때문에 조금 쉽게접근이가능했다.)
==>만약 오름차순으로 배열이 구성되어있지않다면 먼저 오름차순으로 바꿔주는 과정을 거쳐서 푸는것도 나쁘지않아보임

const arr = [-4, -3, -2, -1, 0, 1, 2, 5];

const solution = arr => {
  let left = 0; 
  let right = arr.length - 1; 

  while (left < right) {
    let sum = arr[left] + arr[right];

    if (sum === 0) {
      return [arr[left], arr[right]];
    } else if (sum > 0) {
      right--;
    } else {
      left++;
    }
  }
};

console.log(solution(arr)); // [-2, 2]