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

오늘은 자바를 이용한 알고리즘 문제 해결에서 중요한 기법 중 하나인 “투 포인터” 기법에 대해 알아보겠습니다.
이 기법은 배열이나 리스트를 순회할 때 두 개의 포인터를 사용하는 방법으로, 주로 정렬된 데이터에서 특정한 조건을 찾는 데 많이 사용됩니다.

투 포인터란?

투 포인터 기법은 배열을 두 개의 포인터(또는 인덱스)로 스캔하는 방법입니다.
한 포인터는 배열의 시작을 가리키고, 다른 포인터는 배열의 끝을 가리킵니다.
이 방법은 O(n) 시간복잡도로 문제를 해결할 수 있는 경우가 많기 때문에, 효율적인 알고리즘을 작성하는 데 유용합니다.

문제 설명

이제 아래와 같은 문제를 풀어보겠습니다.
주어진 정수 배열 nums와 정수 target이 있을 때,
배열 내 두 수의 합이 target과 일치하는 인덱스를 찾는 문제입니다.
각 입력에는 항상 해가 존재하며, 같은 요소를 두 번 사용하지 않습니다.

문제 접근 방법

문제를 해결하기 위해 다음과 같은 접근 방식을 따릅니다:

1. 배열을 정렬합니다.
2. 첫 번째 포인터를 배열의 시작, 두 번째 포인터를 배열의 끝에서 시작합니다.
3. 두 포인터가 가리키는 두 값의 합을 계산합니다.
4. 합이 target과 같으면 해당 인덱스를 반환합니다.
5. 합이 target보다 작으면 첫 번째 포인터를 오른쪽으로 이동합니다 (더 큰 수를 찾기 위해).
6. 합이 target보다 크면 두 번째 포인터를 왼쪽으로 이동합니다 (더 작은 수를 찾기 위해).
7. 이 과정을 반복합니다.

자바 코드 구현

이제 위의 알고리즘을 자바로 구현해 보겠습니다.
아래의 코드는 이전에 설명한 투 포인터 접근법을 사용하여 문제를 해결하는 예시입니다.

import java.util.HashMap;

public class TwoSum {
    public int[] twoSum(int[] nums, int target) {
        // 결과를 저장할 해시맵 생성
        HashMap map = new HashMap<>();
        
        // nums 배열을 순회하여 각 요소의 인덱스를 해시맵에 저장
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            // 보완 요소가 해시맵에 존재하는지 확인
            if (map.containsKey(complement)) {
                return new int[] { map.get(complement), i }; // 두 인덱스를 반환
            }
            map.put(nums[i], i); // 현재 요소의 인덱스를 해시맵에 저장
        }
        throw new IllegalArgumentException("No two sum solution");
    }

    public static void main(String[] args) {
        TwoSum ts = new TwoSum();
        int[] nums = { 2, 7, 11, 15 };
        int target = 9;
        int[] result = ts.twoSum(nums, target);
        System.out.println("결과: [" + result[0] + ", " + result[1] + "]");
    }
}

코드 설명

위 코드는 해시맵을 사용하여 문제를 해결합니다.
각 요소를 순회하면서 현재 요소와 더해서 target과 같은 수를 만들 수 있는 보완 요소가 해시맵에 있는지 검사합니다.
보완 요소가 발견되면 해당 인덱스를 반환합니다.
이 방법은 투 포인터 접근법과는 다르지만, 해시맵을 통한 접근도 유용합니다.

복잡도 분석

이 알고리즘의 시간 복잡도는 O(n)입니다. 왜냐하면 배열을 단 한 번만 순회하기 때문입니다.
공간 복잡도는 O(n)으로, 해시맵을 사용하여 모든 요소를 저장하기 때문입니다.
투 포인터 접근법이 사용되지 않았지만, 투 포인터 기법 역시 시간 복잡도가 낮아 유용한 방법입니다.

결론

오늘은 자바를 이용한 알고리즘 문제 해결에서 투 포인터 접근법에 대해 알아보았습니다.
이 기법은 배열이나 리스트에서 특정 조건을 만족하는 문제를 효율적으로 해결하는 데 도움이 됩니다.
다양한 문제를 풀어보면서 이 기법을 익히면 취업용 알고리즘 테스트 준비에 큰 도움이 될 것입니다.

다음 시간에는 특정한 문제를 추가적으로 살펴보며, 응용 형태를 다룰 예정입니다.
더 나아가 투 포인터 기법을 활용한 다른 문제 유형도 함께 고민해보도록 하겠습니다.