.png&blockId=5f7573ad-6867-4d59-999e-722aced04aeb)
덧셈하여 타겟을 만들 수 있는 배열의 두 숫자 인덱스를 리턴하라.
My solution
모든 인덱스를 2개씩 방문하면서 target이 될 때 그 인덱스를 리턴시켰다.
Code
const twoSum = function (nums, target) {
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] === target) {
return [i, j];
}
}
}
return [];
};
JavaScript
복사
이렇게 풀면 매우 간단하지만 시간복잡도가 O(n^2)나 된다.
Solution
1. 브루트 포스로 계산
느리다. 최적화할 여러 방법이 있다.
2. in을 이용한 탐색
target에서 하나의 값을 뺀 값이 존재하는지 탐색해본다.
js로 구현하면 아래와 같다.
const twoSum = function (nums, target) {
for (let i = 0; i < nums.length; i++) {
if (nums.includes(target - nums[i])) {
return [i, nums.indexOf(target - nums[i])];
}
}
return [];
};
JavaScript
복사
3. 첫 번째 수를 뺀 결과 키 조회
딕셔너리에 키와 값을 바꿔서 저장해둔다. 2번에서처럼 타겟에서 하나의 값을 뺀 결과를 키로 조회할 때 쓴다.
딕셔너리는 최악의 경우 조회에 O(n)이 걸리지만 대체로 O(1)이다.
const twoSum = function (nums, target) {
const map = new Map();
// 키와 값 <-> 값과 키
for (let i = 0; i < nums.length; i++) {
map.set(nums[i], i);
}
for (let i = 0; i < nums.length; i++) {
if (map.has(target - nums[i])) return [i, map.get(target - nums[i])];
}
return [];
};
JavaScript
복사
4. 조회 구조 개선
위의 for문은 합칠 수 있다. 두번째 값을 기준으로 찾기
const twoSum = function (nums, target) {
const map = new Map();
for (let i = 0; i < nums.length; i++) {
if (map.has(target - nums[i])) return [map.get(target - nums[i]), i];
map.set(nums[i], i);
}
return [];
};
JavaScript
복사
5. 투 포인터 이용
왼쪽 오른쪽 포인터의 합이 타겟보다 크면 오른쪽을 왼쪽으로 옮기고,
타겟보다 작으면 왼쪽을 오른쪽으로 옮긴다.
맨처음 2, 15에 위치하지만 타겟보다 크므로 오른쪽이 왼쪽으로 옮겨진다.
2,11이 되는데 또 타겟보다 크다. 오른쪽이 왼쪽으로 옮겨진다.
2, 7로 답이 된다.
js로 구현하면 아래와 같다.
const twoSum = function (nums, target) {
nums.sort((a,b)=>a-b);
let left = 0;
let right = nums.length - 1;
while (left < right) {
if (nums[left] + nums[right] === target) {
return [left, right];
}
if (nums[left] + nums[right] < target) {
left++;
} else {
right--;
}
}
return [];
};
JavaScript
복사
시간복잡도 O(n)이지만 원래의 인덱스를 기억해야하므로 정렬이 필요한 투포인터 방식으로 풀 수 없다.
6. Go 구현
빠른 언어로 작성하기. 파이썬보다 6배 빠르다.
