C# 코딩테스트 강좌, 투 포인터

문제 설명

주어진 정수 배열 nums와 정수 target가 있을 때,
nums 배열 내에서 두 수의 합이 target과 같은 인덱스를 찾아 해당 인덱스를 반환하는 문제를 해결하세요.
사용자는 한 쌍의 정수가 반드시 존재한다고 가정합니다.

입력 예시

• nums = [2, 7, 11, 15]
• target = 9

출력 예시

[0, 1]

알고리즘 접근법

이 문제를 해결하기 위해서는 투 포인터 기법을 사용하여 배열을 순회하고,
현재 두 포인터가 가리키는 값의 합을 비교하면서 목표한 값을 찾는 방향으로 접근합니다.
투 포인터 기법은 보통 정렬된 배열에 적용되지만, 이 문제에서는 두 포인터가
같은 배열을 가리키면서 다양한 경우를 고려하는 방법으로 사용될 수 있습니다.

문제 풀이 과정

1. 배열의 두 포인트 초기 인덱스 설정

배열의 시작 포인터 left는 0으로, 마지막 포인터 right는 배열의 길이 – 1로 초기화합니다.
이렇게 하면 nums[left]와 nums[right]를 통해 배열을 탐색할 수 있습니다.

2. 반복 형태로 포인터 이동

예를 들어, 다음과 같은 반복문을 사용하여 두 포인터가 가리키는 값의 합을 비교합니다:

while (left < right) {
                int sum = nums[left] + nums[right];
                if (sum == target) {
                    return new int[] { left, right };
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }

3. 결과 반환

조건에 맞는 left와 right의 인덱스를 찾으면 해당 값을 반환합니다.
만약 조건에 맞는 값이 없다면 null 또는 예외를 반환하도록 처리합니다.

C# 코드 구현

using System;

class Program {
    static void Main(string[] args) {
        int[] nums = { 2, 7, 11, 15 };
        int target = 9;
        int[] result = TwoSum(nums, target);
        Console.WriteLine($"[{result[0]}, {result[1]}]");
    }

    static int[] TwoSum(int[] nums, int target) {
        int left = 0;
        int right = nums.Length - 1;

        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum == target) {
                return new int[] { left, right };
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }

        // 조건에 맞는 쌍을 찾지 못한 경우
        throw new Exception("No two sum solution");
    }
}
            

풀이 분석

1. 시간 복잡도

이 알고리즘의 시간 복잡도는 O(n)입니다.
left와 right 포인터가 한 번씩 배열을 스캔하기 때문에 최악의 경우에도
O(n)으로 성능이 유지됩니다.

2. 공간 복잡도

공간 복잡도는 O(1)입니다. 추가적인 배열이나 리스트를 사용하지 않으므로 공간적 성능이 뛰어납니다.

결론

이번 강좌에서는 투 포인터 알고리즘을 이용하여 간단한 문제를 해결해보았습니다.
투 포인터 기법은 여러 문제에서 매우 유용하게 사용될 수 있으며, 배열이나 리스트를 효과적으로
탐색하는 방법입니다. 앞으로 더 다양한 예제와 함께 이 기법을 더욱 심화학습하면 좋겠습니다.