배열 요소의 조합을 찾는 문제

Q. twoSum 함수에 숫자배열과 '특정 수'를 인자로 넘기면, 더해서 '특정 수'가 나오는 index를 배열에 담아 return해 주세요.

nums: 숫자 배열
target: 두 수를 더해서 나올 수 있는 합계
return: 두 수의 index를 가진 숫자 배열

예를 들어,
nums은 [4, 9, 11, 14] target은 13
nums[0] + nums[1] = 4 + 9 = 13 이죠?
그러면 [0, 1]이 return 되어야 합니다.

# 가정
target으로 보내는 합계의 조합은 배열 전체 중에 2개 밖에 없다고 가정하겠습니다.

 

 

답안

// 내 답안
const twoSum = (nums, target) => {
  // 아래 코드를 작성해주세요.
  let result = [];
  
  for (let i = 0; i < nums.length-1; i++) {
    for (let j = 1; j < nums.length; j++) {
     if (nums[i] + nums[j]  === target) {
     result.push(i, j)
     }
   }
  }
  return result;
}

 

[접근]

1. 배열 요소의 index를 배열에 담아 반환한다.

2. 배열 요소의 합이 target과 같은 두 배열을 찾는다.

 

저 두 가지를 구현하기 위해, 먼저 결과를 넣을 빈 배열을 선언한다.

그리고 배열 내 요소들을 (a, b)의 형태로 두 개씩 짝지어 배열을 순회할 수 있을지 고민했다.

즉, 배열요소의 조합(순열)을 생각했다.

 

i = 0 일 때, j는 1, 2, 3

i = 1일 때, j는 2, 3

i는 2일 때, j는 3

저렇게 더할 수 있도록 짝짓는 방식은 위의 중첩 for문으로 구현이 가능하다.

 

그런데, 더욱 간단하고 직관적으로 코드를 작성할 수는 없을까 고민하던 중

 

정말 좋은 접근을 한 동기의 답안을 보게 되었다.

// 킹갓제너럴 유주님의 답

const twoSum = (nums, target) => {
  // 아래 코드를 작성해주세요.
  let result = [];
  const newArr = nums.map( x => target - x );
  for (let i = 0; i < newArr.length; i++) {
    result.push(nums.includes(newArr[i]));
  }
  return [result.indexOf(true), result.lastIndexOf(true)]
}

또는

const twoSum = (nums, target) => {
  let newArr = nums.map(x => target-x);
  let arr=[];
  for(let i=0; i<nums.length; i++){
  	if(nums.includes(newArr[i])) {
  	arr.push(i);
  	}
  } return arr
}

결국 target은 배열의 안에 있는 요소들의 합이다. 때문에, 각 요소에게 13이 되기 위해 얼마를 더해주어야 하는가(= 더해야 하는 다른 요소의 값)를 알면 된다.

그래서 그 값들을 새로운 배열의 요소로 담아서, 그 요소가 원래 배열의 어느 위치에 있는지를 반환하면 되는 것이다.

 

문제를 복잡하게 중첩 for loop를 쓰기보다,

직관적으로, 간단하게 접근하셔서 코드를 보고 감탄했다.

 

내가 푼 방식은 내가 아는 지식, 문법적으로 어떻게 문제를 해결할 수 있을까,

for loop도 적용해보고, 여러 메소드들을 먼저 접근해보다가 풀이가 얻어걸린 느낌이라면

 

동기의 방식은 자신이 세운 로직에 의해 컴퓨터가 움직이도록 코드를 작성한 것 같다는 느낌이 들었다.

 

앞으로, 문제에 접근할 때 문제의 표면에 주어진 정보로만 접근하기보다,

문제를 단순화 시켜서 접근하는 연습을 해야겠다.

 

물론, 복잡한 것을 단순화 하는 것은 매우 내공이 필요한 일이니까.. 잘 될지는 모르겠다^^