오늘은 자바를 이용한 알고리즘 문제 해결에서 중요한 기법 중 하나인 “투 포인터” 기법에 대해 알아보겠습니다.
이 기법은 배열이나 리스트를 순회할 때 두 개의 포인터를 사용하는 방법으로, 주로 정렬된 데이터에서 특정한 조건을 찾는 데 많이 사용됩니다.
투 포인터란?
투 포인터 기법은 배열을 두 개의 포인터(또는 인덱스)로 스캔하는 방법입니다.
한 포인터는 배열의 시작을 가리키고, 다른 포인터는 배열의 끝을 가리킵니다.
이 방법은 O(n) 시간복잡도로 문제를 해결할 수 있는 경우가 많기 때문에, 효율적인 알고리즘을 작성하는 데 유용합니다.
문제 설명
이제 아래와 같은 문제를 풀어보겠습니다.
주어진 정수 배열 nums와 정수 target이 있을 때,
배열 내 두 수의 합이 target과 일치하는 인덱스를 찾는 문제입니다.
각 입력에는 항상 해가 존재하며, 같은 요소를 두 번 사용하지 않습니다.
nums = [2, 7, 11, 15], target = 9예제 출력:
[0, 1] (2 + 7 = 9)
문제 접근 방법
문제를 해결하기 위해 다음과 같은 접근 방식을 따릅니다:
- 배열을 정렬합니다.
- 첫 번째 포인터를 배열의 시작, 두 번째 포인터를 배열의 끝에서 시작합니다.
- 두 포인터가 가리키는 두 값의 합을 계산합니다.
- 합이
target과 같으면 해당 인덱스를 반환합니다. - 합이
target보다 작으면 첫 번째 포인터를 오른쪽으로 이동합니다 (더 큰 수를 찾기 위해). - 합이
target보다 크면 두 번째 포인터를 왼쪽으로 이동합니다 (더 작은 수를 찾기 위해). - 이 과정을 반복합니다.
자바 코드 구현
이제 위의 알고리즘을 자바로 구현해 보겠습니다.
아래의 코드는 이전에 설명한 투 포인터 접근법을 사용하여 문제를 해결하는 예시입니다.
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)으로, 해시맵을 사용하여 모든 요소를 저장하기 때문입니다.
투 포인터 접근법이 사용되지 않았지만, 투 포인터 기법 역시 시간 복잡도가 낮아 유용한 방법입니다.
결론
오늘은 자바를 이용한 알고리즘 문제 해결에서 투 포인터 접근법에 대해 알아보았습니다.
이 기법은 배열이나 리스트에서 특정 조건을 만족하는 문제를 효율적으로 해결하는 데 도움이 됩니다.
다양한 문제를 풀어보면서 이 기법을 익히면 취업용 알고리즘 테스트 준비에 큰 도움이 될 것입니다.
다음 시간에는 특정한 문제를 추가적으로 살펴보며, 응용 형태를 다룰 예정입니다.
더 나아가 투 포인터 기법을 활용한 다른 문제 유형도 함께 고민해보도록 하겠습니다.