오늘의 알고리즘 문제 자바스크립트로 풀기!

문제는 위와 같다.

사실 이 문제를 보자마자 떠오른 건 이중포문을 돌려서 조건에 일치하는 index 값들을 배열화하여 리턴하는 것이었다. 생각한 방식은 다음과 같다.

const twoSum = (nums, target) => {
	for(let i = 0; i<nums.length; i++){
    for(let j = i + 1; j <nums.length; j++){
    	if(arr[i] + arr[j] === target) return [i,j]
}}}

그런데 사실 배열 내 아이템이 4개라 얼마 안걸릴지 몰라도 이게 규모가 커져버리면 계속 n의 제곱만큼의 경우의 수를 돌아야하니까 좀 낭비같다는 생각이 들었다.

굳이 이중포문을 돌지 않고도 분명 더 효율적으로, 빠르게 답을 구할 수 있는 방식을 계속 고민하고 검색하던 중 알아낸 방식이 있다(!)

바로 객체를 활용한 방식이다.

풀이는 아래와 같다.

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

빈 객체를 만든 후, 0부터 nums의 마지막 index까지 for문을 돈다.
그리고 target에서 배열의 해당 아이템을 뺀 값을 complement라는 변수 안에 담아준다.
객체에는 key값으로 nums의 value값을, 객체의 value 값으로는 index을 채워주는 방식이다.
ex) obj = {4 : 0, 9 : 1 }
그리고 만약에 complement가 obj의 key값으로 존재한다면, 그 key의 value값과 (즉 index 값)과 포문을 돌리고 있던 해당 아이템의 index 값을 return해주는 방식이다.

이렇게 로직을 짜게 되면, 굳이 이중포문을 돌지 않아도, 정답을 찾아내면 바로 함수를 return함으로써 최대 n의 경우의 수로만 for문을 돌게 되니까 훨씬 효율적이다.

그리고 꼭 객체가 아니더라도, Map으로도 같은 로직에 의하여 풀 수 있다.

const twoSum = (nums, target) => {
  let map = new Map();

    for(let i = 0; i<nums.length ; i++){
    let complement = target - nums[i];
    if(map.has(complement) !== undefined){
      return [map.get(complement), i]
    }
    map.get(nums[i]) = i
  }

}

빈 객체를 만드는 대신 Map을 생성하여 내장함수를 이용하여 같은 로직에 의하여 푸는 방식이다.

느낀 점

문제를 풀 때 어떻게 빨리 풀어버릴까 고민하기 보다는 어떻게 효율적으로 잘 풀 수 있을지를 계속 고민해봐야겠다. 많은 풀이 방법 중에서 최대한 효율적인 답을 잘 도출해내고 싶다! 꾸준히 고민하고 생각하는 개발자가 되자👊 🔥