자바스크립트 코딩테스트 강좌, 투 포인터

코딩테스트에서 자주 등장하는 알고리즘 중 하나인 투 포인터(Two Pointer) 기법에 대해 자세히 알아보겠습니다. 본 강좌에서는 투 포인터의 기본 개념을 설명하고, 이를 활용한 실제 문제를 해결해보겠습니다.

1. 투 포인터(Two Pointer)란?

투 포인터 기법은 배열이나 리스트와 같은 데이터 구조에서 두 개의 포인터를 이용하여 효율적으로 데이터를 처리하는 알고리즘 기법입니다. 일반적으로 문제의 크기가 커질수록 불필요한 반복문을 줄이고, 시간 복잡도를 개선하는 데 효과적입니다.

  • 효율성: 시간 복잡도를 O(N)으로 줄여주는 경우가 많습니다.
  • 간결함: 코드가 간단해지고 가독성이 향상됩니다.
  • 적용 범위: 정렬된 배열, 문자열, 서브 배열(subarray) 문제 등 다양한 상황에서 사용할 수 있습니다.

2. 투 포인터의 기본 아이디어

투 포인터는 일반적으로 다음과 같은 두 가지 방법으로 사용됩니다:

  • 왼쪽과 오른쪽 포인터: 배열의 양 끝에서 시작하여 중앙으로 이동하며 조건을 만족하는 요소를 찾습니다.
  • 같은 방향으로 이동: 두 포인터가 같은 방향으로 이동하면서 특정 조건을 만족할 때까지 주변 요소를 검사합니다.

3. 실제 문제: 두 수의 합

다음은 투 포인터를 사용한 실제 문제입니다.

문제 설명

정렬된 배열 numbers와 목표 합 target이 주어질 때, 두 수의 합이 목표 합과 일치하는 두 수의 인덱스를 반환하는 함수를 작성하세요. 각 입력에는 정확히 하나의 해답이 존재한다고 가정하며, 같은 요소를 두 번 사용할 수는 없습니다.

입력 형식

numbers: [2, 7, 11, 15]
target: 9

출력 형식

[0, 1]

예제 설명

위 예제에서 2 + 7 = 9이므로 출력은 인덱스 0과 1입니다.

4. 문제 해결 과정

투 포인터를 사용하여 이 문제를 해결해보겠습니다. 다음 단계로 진행합니다:

Step 1: 포인터 초기화

배열의 시작과 끝에 포인터를 초기화합니다. 왼쪽 포인터는 left, 오른쪽 포인터는 right로 명명합니다.

Step 2: 조건 검사

While 루프를 사용하여 두 포인터가 교차할 때까지 반복합니다. 각 반복마다 현재 포인터가 가리키는 두 수의 합을 계산하고, 이 합이 target과 일치하는지 확인합니다.

Step 3: 합 비교

  • 합이 target보다 작으면 left 포인터를 하나 오른쪽으로 이동합니다.
  • 합이 target보다 크면 right 포인터를 하나 왼쪽으로 이동합니다.
  • 합이 target과 같으면 두 인덱스를 반환합니다.

Step 4: 코드 구현

function twoSum(numbers, target) {
        let left = 0; 
        let right = numbers.length - 1;

        while (left < right) {
            const sum = numbers[left] + numbers[right];

            if (sum === target) {
                return [left, right]; 
            } else if (sum < target) {
                left++; 
            } else {
                right--; 
            }
        }
        return []; // 해답이 없는 경우
    }

Step 5: 코드 분석

이 코드의 시간 복잡도는 O(N)이며, 공간 복잡도는 O(1)입니다. 즉, 배열을 추가로 저장하지 않고도 문제를 해결할 수 있습니다.

5. 추가 예제 및 변형 문제

이제 다른 변형 문제를 살펴보겠습니다. 주어진 배열에서 세 수의 합이 target과 일치하는 모든 조합을 찾는 문제로 응용할 수 있습니다.

문제 설명

정수 배열 numbers와 정수 target이 주어질 때, 세 수의 합이 target이 되는 모든 조합의 인덱스를 반환하세요. 결과는 중복되지 않도록 합니다.

입력 형식

numbers: [1, 2, 3, 4, 5]
target: 9

출력 형식

[[0, 3, 4], [1, 2, 4], [2, 3, 4]]

해결 접근 방식

이 문제를 해결하기 위해, 두 번째 포인터를 추가하여 중복되지 않는 조합을 찾는 방법을 사용할 수 있습니다. 수정된 알고리즘은 다음과 같습니다:

function threeSum(numbers, target) {
        let result = [];
        numbers.sort((a, b) => a - b); // 배열 정렬

        for (let i = 0; i < numbers.length - 2; i++) {
            let left = i + 1;
            let right = numbers.length - 1;

            while (left < right) {
                const sum = numbers[i] + numbers[left] + numbers[right];

                if (sum === target) {
                    result.push([i, left, right]);
                    left++;
                    right--;
                    while (left < right && numbers[left] === numbers[left - 1]) left++; // 중복 제거
                    while (left < right && numbers[right] === numbers[right + 1]) right--; // 중복 제거
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return result;
    }

6. 마무리

투 포인터는 배열이나 리스트를 처리하는 데 있어 매우 유용한 기법입니다. 특히 정렬된 데이터를 다룰 때 성능을 획기적으로 개선할 수 있습니다. 본 강좌에서 다룬 내용을 통해 투 포인터의 기본 개념과 활용 방법을 이해하고, 실전 문제를 해결하는 데 도움이 되기를 바랍니다.

탐색 및 조합 문제에서 투 포인터를 사용할 수 있는 다양한 상황을 계속 연습하시고, 실제 코딩 인터뷰에서도 자신 있게 활용하시기 바랍니다.

연습 문제

다음 문제를 연습해 보세요:

  • 정수 배열 numbers와 정수 target이 주어질 때, 가장 가까운 두 수의 합이 target이 되는 인덱스의 조합을 반환하는 문제
  • 문자열 내에서 유일한 문자로 이루어진 서브스트링(substring)의 길이를 반환하는 문제

이와 같은 문제를 통해 투 포인터의 이해도를 높이고, 다양한 문제를 해결하는 경험을 쌓아보세요.