[알고리즘] LeetCode - Two Sum

보통인부·2020년 7월 10일
1

노가다 알고리즘

목록 보기
1/10
post-thumbnail

리트코드 문제풀이 - Two Sum


<문제>

Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each input would have exactly one solution, and you may not use the same element twice.

<예시>

Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

<해설>

nums 인수로 주어진 정수 배열에서 두 수를 추출하여 더했을 때 target값이 되는 두 배열요소의 index를 배열 형태로 리턴하시오. 같은 요소를 두번 고르면 안됨. 정답은 반드시 하나 뿐임.

처음에 뭐 이런거까지 풀어야되낰ㅋㅋㅋ 하고 깝치다가 엄청 털림.
문제를 꼼꼼히 읽어야 되는데 서밋 할때마다 '요건 몰랐지?'하고 놀리듯이 예외케이스를 내놓더라.

첫번째) 같은 수를 두번 고르면 안된다길래 단순하게 고른 두 수가 같으면 continue로 넘겼는데 index는 다르지만 같은 숫자인 element들이 들어 있는 경우도 있었음^^
두번째) 사전에 target보다 큰 수는 죄다 필터링 해서 미리 걸렀는데 알고보니 자연수가 아니라 정수였음^^

빡쳐서 그냥 brute force로 다 돌려버림.
문제는 풀었는데...

Your runtime beats 15.66 % of javascript submissions!

음... 내 밑에 15.66%?? 뭔데 나머진 그럼

응 hash map ^ㅡ^

아... 결국 다시 품

최종코드

var twoSum = function (nums, target) {
  const hashMap = {};
  nums.forEach((num, i) => {
    hashMap[num] = i;
  });

  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (hashMap[complement] && hashMap[complement] !== i) {
      return [i, hashMap[complement]];
    }
  }
};

Runtime: 64 ms, faster than 90.14% of JavaScript online submissions for Two Sum.

😎 야호!

0개의 댓글