# 문제
정수 배열 nums 과 정수가 주어지면 target, 두 숫자의 인덱스를 반환하여 두 숫자의 합이target . 가 되도록 합니다.
각 입력에 대한 해답은 정확히 하나만 있다고 가정할 수 있으며 , 같은 요소를 두 번 사용할 수 없습니다 . 어떤 순서로든 답변을 제출할 수 있습니다.
예시 1:
입력: nums = [2,7,11,15], target = 9
출력: [0,1]
설명: nums[0] + nums[1] == 9이므로 [0, 1]을 반환합니다.
예시 2:
입력: nums = [3,2,4], target = 6
출력: [1,2]
예시 3:
입력: nums = [3,3], target = 6
출력: [0,1]
제약사항:
- 2 <= nums.length <= 104
- -109 <= nums[i] <= 109
- -109 <= target <= 109
- 유효한 답은 오직 하나뿐입니다.
후속 질문: 시간 복잡도 보다 낮은 알고리즘을 만들어낼 수 있나요 ?O(n2)
# 해설
twoSum함수는 주어진 배열 nums와 목표값 target을 이용하여 배열의 두 숫자의 합이 target과 일치하는 두 숫자의 인덱스를 찾는 문제를 해결하는 함수이다.
두가지 접근 방법이 있다
1. 브투스포스 (Brute Force) = 이중루프를 사용하여 모든 쌍을 검사한다.
이 방법은 간단하지만 시간복잡도가 O(n2)이다. 배열의 크기가 크면 성능이 좋지 않지만 이해하기는 쉬움
(개인적으로 이게 읽기 편하다ㅠ)
function twoSum(nums: number[], target: number): number[] {
// 배열의 길이만큼 반복
for (let i = 0; i < nums.length; i++) {
// i번째 숫자와 다른 숫자들을 비교
for (let j = i + 1; j < nums.length; j++) {
// 두 숫자의 합이 목표값과 같은지 확인
if (nums[i] + nums[j] === target) {
// 목표값을 만드는 두 숫자의 인덱스를 반환
return [i, j];
}
}
}
// 목표값을 만드는 쌍이 없으면 빈 배열 반환
return [];
}1) 이중루프 사용 = 배열을 두번 반복하여 모든 가능한 쌍을 검사한다
(1) 첫번째 루프는 배열의 각 숫자를 선택
(2) 두번째 루프는 선택된 숫자 이후의 모든 숫자를 검사한다
2) 합 비교 = 현재 선택된 두 숫자의 합이 target과 같은지 확인
3) 인덱스 반환 = 합이 target과 같으면 두 숫자의 인덱스를 배열형태로 반환
4) 결과 없음 = 만약 어떤 쌍도 목표값을 만들지 않는다면 빈 배열 반환
2. 해시맵 = 해시맵을 사용하여 이미 본 숫자와의 쌍을 찾는다
해시맵 접근법이 더 효율적이고 시간 복잡도가 O(n)이고 공간 복잡도 또한 O(n)이다
function twoSum(nums: number[], target: number): number[] {
const numMap = new Map<number, number>(); // 숫자와 그 인덱스를 저장할 해시 맵
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i]; // 목표값에서 현재 숫자를 뺀 값
if (numMap.has(complement)) {
// 보완 숫자가 해시 맵에 존재하면, 쌍을 찾은 것이므로 인덱스를 반환
return [numMap.get(complement)!, i];
}
// 현재 숫자와 인덱스를 해시 맵에 추가
numMap.set(nums[i], i);
}
// 유효한 쌍을 찾지 못한 경우, 빈 배열을 반환 (문제 설명에 따라 필요 시)
return [];
}1) 해시맵 생성 = numMap은 숫자와 그 숫자의 인덱스를 저장함
2) 루프를 통한 처리
- 현재숫자 nums[i]에 대해, target에서 nums[i]를 뺀 값을 complement로 계산한다
- complement가 numMap에 존재하는지 확인하고,
- 존재하면 complement와 현재 숫자가 목표 값을 만드는 쌍이므로 그 인덱스를 반환한다
- 존재하지 않으면 현재 숫자와 인덱스를 해시 맵에 추가한다
3) 해시 맵 사용 = 해시 맵을 사용하여 이전에 본 숫자들을 빠르게 확인할 수 있다
이 방식은 배열을 한번만 순회하기에 시간효율성이 좋다. 아 코드는 nums배열에서 두 숫자의 인덱스를 찾아 target에 맞는 쌍을 반환한다
