Algorithm - CodeKata #01

1. Question

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개 밖에 없다고 가정하겠습니다.

2. Try

우선 배열에서 인덱스를 배출하기 위해서는 for 문이 필요할 것 같다고 생각했다.

아래와 같은 코드를 작성하면 [0], [1], [2], [3]이 차례로 출력된다.

const nums = [4, 9, 11, 14];

for (let i = 0; i <nums.length; i++) {
	console.log([i]);
}

그럼 여기서 두 개의 인덱스가 배열로 출력되어야 하니 아래와 같이 시도해보면

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

for 문에서 i값이 3일 때, if문에서 nums[3] + nums[4]가 되므로 이 코드는 틀린 코드이다.

배열 nums의 길이가 4이며, nums[4]는 정의되어 있지 않기 때문이다.

그럼 여기서 이중 for 문을 써본다면?

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

첫 번째 for 문에서 조건에 nums.length-1을 해준 이유는 안에 for 문이 한 번 더 포함되어 있으니,

그 for 문에서 마지막에 출력하는 값이 배열의 마지막 인덱스가 되어야 하기 때문이다.

위의 코드에서 for 문이 돌아가는 방식을 차례대로 해석해 보겠다.

1. 첫 번째 for 문의 i가 0일 때

• j = 1, 만약 nums[0] + nums[1]이 target이라면, 배열 [0, 1]을 출력한다.
• j = 2, 만약 nums[0] + nums[2]이 target이라면, 배열 [0, 2]을 출력한다.
• j = 3, 만약 nums[0] + nums[3]이 target이라면, 배열 [0, 3]을 출력한다.

2. 첫 번째 for 문의 i가 1일 때

• j = 2, 만약 nums[1] + nums[2]이 target이라면, 배열 [1, 2]을 출력한다.
• j = 3, 만약 nums[1] + nums[3]이 target이라면, 배열 [1, 3]을 출력한다.

3. 첫 번째 for 문의 i가 2일 때

• j = 3, 만약 nums[2] + nums[3]이 target이라면, 배열 [2, 3]을 출력한다.

  
  

3. Answer

const twoSum = (nums, target) => {
   for (let i = 0; i < nums.length-1; i++) {
       for (let j = i + 1; j < nums.length; j++) {
         if (nums[i] + nums[j] === target) {
           return [i, j];
         }
       }
   }
}
 
console.log(twoSum([4, 9, 11, 14], 13)); // [ 0, 1 ]
console.log(twoSum([4, 9, 11, 14], 15)); // [ 0, 2 ]
console.log(twoSum([4, 9, 11, 14], 18)); // [ 0, 3 ]
console.log(twoSum([4, 9, 11, 14], 20)); // [ 1, 2 ]
console.log(twoSum([4, 9, 11, 14], 23)); // [ 1, 3 ]
console.log(twoSum([4, 9, 11, 14], 25)); // [ 2, 3 ]

사실 처음에 -1은 붙이지 않은 채로 제출했다.

그런데 채점 에러였나보다.. 통과가 되었다.