[알고리즘] Two pointer method

문제 1)

✍️ 내 풀이 - 중첩 for문 사용

    let index = [0, 1];
    
    if (nums.length === 2) {
        return index;
    }
    

    for (let i = 0; i < nums.length; i++) {
        for (let j = 0; j < nums.length; j++) {
            if (nums[i] + nums[j + i + 1] === target) {
                return [i, j + i + 1];
            }
        }
    }
    
    return null;

두 자리 배열일 경우 early return을 시켜주고, 중첩 for문을 이용해서 왼쪽을 기점으로 하나씩 비교해준 뒤 target값과 합이 같을 시에 return 을 시켜주었다.

✏️ 다른 사람 풀이

Solution 2. Memorization

• One-pass Hash Table
  해시맵을 이용하여 기존의 값을 기억해두어 한 번의 반복문을 사용하여 해결.

const twoSum = (nums, target) => {
  const map = {};

  for (let i = 0; i < nums.length; i++) {
    const another = target - nums[i];

    if (another in map) { // map 안에 찾고자하는 요소가 있을 경우
      return [map[another], i]; // 요소와 인덱스를 반환
    }

    map[nums[i]] = i; // 맵 안에 일치하는 요소가 없을 시, 요소를 키 값으로 벨류 값으로 인덱스를 저장해준다.
  }

  return null; // 반복문을 다 돌고도 일치하는 값이 없을 경우에는 null를 반환해준다.
};

중첩으로 반복문을 돌리지 않고 객체 안에 요소의 값과 인덱스를 기억해주어 해당 객체 안에 값이 존재하는지 계속 확인을 시켜주는 구조이다.

target 값에서 현재의 요소 값을 빼면 찾아야 하는 요소의 값을 알 수 있다. 반복문을 돌 때 요소를 객체 안에 저장을 해주면 반복문을 돌지 않아도 해당하는 요소가 존재하는지 체크를 할 수 있다.

---

문제 2)

Two Sum II - Input Array Is Sorted

위에서 푼 것과 같은 방식으로 풀어준 뒤 return 하는 index값에서 +1씩만 더 해주었는데 다른 풀이 방식을 보고 투 포인터 방식을 알게 되었다. 이전까지 생각해보지 못한 새로운 접근 방식이어서 더 재밌게 다가왔는데 투 포인터는 정렬된 배열에서 쌍을 검색하는 데 일반적으로 사용되는 정말 쉽고 효과적인 기술이라고한다. 뜻 그대로 "두 개의 포인터"를 기준으로 정렬된 알고리즘을 푸는 것이다.

또한 위 풀이에서 나는 중첩 반복문을 사용하여 시간/공간 복잡도가 n 제곱이었지만 아래와 같이 풀게되면 0(n)의 복잡도를 가지게 된다.

이전 풀이에서는 중첩 for문은 왼쪽을 기점으로만 2번의 반복문을 돌게 해주었다면, 현재는 양쪽을 기점으로 반복문을 돌려주는 것이다.

👉 Two pointer method

var twoSum = function (numbers, target) {
  let i = 0;
  let j = numbers.length - 1;
  
  while (i !== j) {
    if (numbers[i] + numbers[j] > target) {
      j--;
    } else if (numbers[i] + numbers[j] < target) {
      i++;
    } else {
      return [i + 1, j + 1];
    }
  }
};

알고리즘을 풀 때마다 느끼는 것은 어떻게 더 시간복잡도와 공간복잡도를 줄일 수 있는지, 다른 사람이 보았을 때 이해하기 쉬운 코드인지, 여러 방면에서 더 좋은 코드를 짜기위한 리팩토링이 가장 중요한 점인 것 같다.
출처) leetcode