📑 문제
오름차순으로 정렬된 배열에서 두 수의 합이 특정 타겟 숫자와 같도록 하는 두 수의 인덱스를 찾으세요.
📑 접근방법
이 문제를 처음 보았을 때, '두 수의 합'이라는 키워드가 눈에 띄었습니다. 그래서 바로 '투 포인터(Two Pointer)' 알고리즘을 활용하는 것이 이 문제의 해결책일 것 같다는 생각이 들었습니다.
-
처음에는 단순히 배열의 양 끝에서부터 시작해서 중앙으로 이동하면서 각 위치의 숫자들을 더해보면 어떨까 생각했습니다.
하지만, 문제를 다시 읽어보니 인덱스 값은 1부터 시작하는 것이라는 조건을 확인하였습니다 -
그래서 최종적으로 반환할 때 각각의 인덱스 값에 1을 추가해서 반환하도록 했습니다.
-
우선, left와 right라는 두 개의 포인터를 사용하여 배열의 양 끝에서부터 중앙으로 이동하면서 각 위치에 있는 숫자들의 합을 계산합니다. 이때, 만약 그 합이 타겟 값과 일치한다면, 반복문을 종료하고 해당 인덱스 값을 반환합니다.
-
그리고 만약 현재 left와 right 위치에서 구한 합계가 타겟보다 작다면 left를 증가시켜 다음 요소로 넘어갑니다.
-
반대로 합계가 타겟보다 크다면 right를 감소시켜 이전 요소로 돌아갑니다. 이렇게 하여 가능한 모든 조합을 검사하게 됩니다.
📑 CODE
import java.util.*;
class Solution {
public int[] twoSum(int[] numbers, int target) {
int left = 0;
int right = numbers.length - 1;
int answer[] = new int[2];
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) {
break;
} else if (sum < target) {
left++;
} else {
right--;
}
}
answer[0] = left+1;
answer[1] = right +1;
return answer;
}
}
다른 접근방법
똑같이 Two pointer 알고리즘을 썼지만, 내 코드 처럼 분기를 많이 나누지 않고 간결하게 작성하였습니다.
무식하게 풀지않고 알맞는 알고리즘을 적용해서 푸는 것도 좋지만, 시간복잡도와 공간복잡도를 고려해서 코드를 간결하게 짜는 연습도 해봐야될것같습니다.
public int[] twoSum(int[] nums, int target) {
int l = 0, r = nums.length - 1;
while (nums[l] + nums[r] != target) {
if (nums[l] + nums[r] < target) l++;
else r--;
}
return new int[] {l+1, r+1};
}