0. 문제
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
주어진 배열 요소 두개의 합이 타겟과 일치할 시 해당 배열의 두 인덱스를 반환한다.
#1
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
#2
Input: nums = [3,2,4], target = 6
Output: [1,2]
#3
Input: nums = [3,3], target = 6
Output: [0,1]
1.언어
자바스크립트(JavaScript)
2. 문제 풀이
2-1. 중첩 반복문 - 단순 비교
var 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])
};
간단하게 반복 문 두개로 단순비교로 작성했더니 런타임 하위 19퍼가 나왔다.
2-2. IndexOf
var twoSum = function(nums, target){
let arr=new Array(nums.length), index;
for (let i=0; i<nums.length; i++){
index = arr.indexOf(target-nums[i])
if (index !== -1) return [index,i]
arr[i]=nums[i]
}
};
Runtime: 203 ms, faster than 19.38% of JavaScript online submissions for Two Sum.
Memory Usage: 43.1 MB, less than 33.34% of JavaScript online submissions for Two Sum.
indexOf를 사용해서 다시 풀어보니 똑같이 하위 19퍼가 나왔다.
indexOf 시간 복잡도를 검색해보니 O(n)...... 봤던 거 같은데... 복습를 열심히 하자
2-3 key : value 활용
var twoSum = function(nums, target){
map={};
for (let i=0; i<nums.length; i++){
const anr = target-nums[i];
if (anr in map) return [map[anr],i];
map[nums[i]]=i;
}
}
드디어 77.47..... key : value의 시간 복잡도는 O(1)이라고 한다.
나는 무슨 문제든 풀 때 배열로 해결하려드는 경향이 심한데 앞으로 key : value 를 자주 활용하자.
'LeetCode > 코딩 테스트 스터디 1주차' 카테고리의 다른 글
[LeetCode] 3. Longest Substring Without Repeating Characters 풀이 (0) | 2022.07.10 |
---|---|
[LeetCode] 2. Add Two Numbers 풀이 (0) | 2022.07.10 |
[LeetCode] 14. Longest Common Prefix 풀이 (0) | 2022.07.10 |
[LeetCode] 13. Roman to Integer 풀이 (0) | 2022.07.10 |
[LeetCode] 9. Palindrome-Number 풀이 (0) | 2022.07.10 |