[리트코드] 1. Two Sum
안녕하세요. 개발조각입니다.😊
리트코드에서 첫 문제를 풀었습니다,
일단 Easy를 어느 정도 풀어보려고 합니다.
그럼 1. Two Sum 문제 해결방안에 대해 설명하겠습니다.
https://leetcode.com/problems/two-sum/
Two Sum - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
💚 번역기 돌리면
정수 숫자의 배열과 정수 목표값이 주어지면 목표값에 더해지도록 두 숫자의 인덱스를 반환합니다.
각 입력에 정확히 하나의 솔루션이 있다고 가정할 수 있으며, 동일한 요소를 두 번 사용할 수 없습니다.
답변은 임의의 순서로 반환할 수 있습니다.
후속 조치: 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를 해줍니다.