[리트코드] 1. Two Sum

안녕하세요. 개발조각입니다.😊

리트코드에서 첫 문제를 풀었습니다,

일단 Easy를 어느 정도 풀어보려고 합니다.

 

그럼 1. Two Sum 문제 해결방안에 대해 설명하겠습니다.

---

https://leetcode.com/problems/two-sum/

Two Sum - LeetCode

 

💚 번역기 돌리면

정수 숫자의 배열과 정수 목표값이 주어지면 목표값에 더해지도록 두 숫자의 인덱스를 반환합니다.
각 입력에 정확히 하나의 솔루션이 있다고 가정할 수 있으며, 동일한 요소를 두 번 사용할 수 없습니다.
답변은 임의의 순서로 반환할 수 있습니다.

후속 조치: O(n2) 시간 복잡도보다 작은 알고리즘을 생각해 낼 수 있습니까?

---

접근방법

O(n2) 시간 복잡도보다 작은 알고리즘을 구하라 했으니이중 for문은 안 되겠다고 생각했습니다.

(for문 시간 복잡도: O(n), 이중 for문 시간 복잡도: O(n2))

 

그래서 for문을 한 번만 쓰고 최대한 내장 함수로 해결해봐야겠다고 생각했습니다.

---

해결방안

기존 풀이 방식의 Runtime이 너무 올래 걸리는 것 같아서

다시 수정해보았습니다.

 

새롭게 푼 방식

var twoSum = function(nums, target) {
    let [x, y] = [0, 0]
    const arr = [];
    
    while(1){
        arr.push(nums.shift());
        
        const remainder = target-arr[arr.length-1];
        const requiredIdx = nums.indexOf(remainder);
        
        if(requiredIdx > -1){
            x = arr.length-1;
            y = requiredIdx+arr.length;
            break;
        }
    }
    return [x, y]
};

 

아래와 같은 예제가 있으면

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

 

arr.push(nums.shift());

 nums = [7, 11, 15], arr=[2]가 됩니다.

 

const remainder = target-arr[arr.length-1];

remainder = 7이 됩니다.

 

const requiredIdx = nums.indexOf(remainder);

indexOf를 사용하여 nums에서 remainder값이 있는지 확인합니다.

requiredIdx = 0;

 

if(requiredIdx > -1){
    x = arr.length-1;
    y = requiredIdx+arr.length;
    break;
}

만약 nums에 remainder값이 있으면 x, y에 해당 값을 넣고 break 해줍니다.

---

기존 풀이 방식

var twoSum = function(nums, target) {
    let [x, y] = [0, 0]
    for(let i=0; i<nums.length; i++){
        let arr = nums.slice(i+1);
        let remainder = arr.indexOf(target-nums[i]);

        if(remainder > -1){
            x = i;
            y = remainder+i+1;
            break;
        }
    }
    return [x, y]
};

 

아래와 같은 예제가 있으면

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

 

nums배열에서 i값의 뒤쪽에 있는 원소를 arr배열에 담아줍니다.

(slice를 사용해서 풀었습니다.)

• i가 0일 경우: arr = [7, 11, 15]
• i가 1일 경우: arr = [11, 15]
• i가 2일 경우: arr = [15]

 

arr배열에 target-nums[i]인 원소가 있는 위치를 remainder변수에 담아줍니다.

(indexOf를 사용해서 풀었습니다. 없을 경우 -1이 나옵니다.)

• i가 0일 경우: remainder = 0
• i가 1일 경우: remainder = -1
• i가 2일 경우: remainder = -1

 

만약 remainder가 -1보다 크다면(arr배열에 target-nums[i]인 원소가 있다면)

x에는 i, y에는 remainder+i+1를 넣어주고 break를 해줍니다.