[LeetCode] 1. Two Sum

문제 출처: https://leetcode.com/problems/two-sum/

Two Sum - LeetCode

 

문제

정수 배열 nums와 정수 target이 주어지면, 두 숫자의 합이 target을 만드는 인덱스를 반환하라.

 

각 입력에는 정확히 한 개의 답이 존재하고, 같은 원소를 두 번 사용하지 않아야 한다.

 

순서와 관계없이 답을 반환하라.

 

예제

Input: nums = [2,7,11,15], target = 9
Output: [0,1]

Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Input: nums = [3,3], target = 6
Output: [0,1]

 

풀이

리트코드의 첫 문제인 만큼 난이도가 높은 문제는 아니다. 비교적 쉬운 문제로 분류되는 만큼 다양한 방법으로 문제 풀이가 가능하다.

1. 이중 반복문
2. 정렬 후, 이진 탐색
3. 정렬 후, 투 포인터
4. 맵 자료구조

여기서는 투 포인터 방식을 사용하여 문제에 접근하였다.

• 최초 배열 nums를 인덱스와 엮는다. ( 최종 반환해야 하는 값이 인덱스이기 때문 )
• 인덱스와 값이 엮인 배열을 값 순으로 정렬한다.
• 투 포인터 방식을 이용하여 target을 만드는 쌍을 찾는다. ( lo 포인터: 배열의 첫 요소, hi 포인터: 배열의 마지막 요소 )

var twoSum = function(nums, target) {
    const list = nums.map((val, idx) => [val, idx]);
    
    list.sort((a, b) => a[0] - b[0]);
    
    let lo = 0, hi = nums.length-1;
    while (list[lo][0] + list[hi][0] != target) {
    	if (list[lo][0] + list[hi][0] > target) {
        	hi -= 1;
        } else {
        	lo += 1;
        }
    }
    return [list[lo][1], list[hi][1]];
}

이 방식의 시간복잡도는 정렬에 소요되는 시간복잡도에 의존적일 것이기 때문에 O(nlogn)이 될 것이다.

 

Github: 1.js

GitHub - opwe37/Algorithm-Study