Code Kata_twoSum

문제

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

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

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

예를 들어,
nums은 [4, 9, 11, 14] target은 13

nums[0] + nums[1] = 4 + 9 = 13 이죠?

그러면 [0, 1]이 return 되어야 합니다.

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

풀이

1. 배열을 순회한다.
2. 요소보다 index가 큰 것을 순회하며
3. target이 되었을 때
4. index를 배열에 담아 return

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];
    }
  }
}

빅오표기법

알고리즘의 효율성을 표기해주며, 보통 알고리즘의 시간 복잡도와 공간 복잡도를 나타내는데 사용한다. 알고리즘 최악의 경우 복잡도를 측정한다. 상수항(ex|2n에서 2)과 영향력이 없는 항(n^2 + n에서 n)은 무시한다. 항상 n 변수 이외에 여려 개의 변수가 사용되는 경우도 있으니 유념하자.

O(1) < O(logn) < O(n) < O(n lon n) < O(n^2) < O(2n^2) 순으로 큰 시간 복잡도를 가져 비효율적이다. 간단하게 시간 복잡도를 비교해보자.

//O(1)

(1+n)/2

//O(n)
const sum = 0;
for(i=1; i<=n; i++) {
  sum = sum + i
}

//O(n^2): 보통 중첩된 반복문을 사용하는 알고리즘(일반적으로 좋지 않음)
for(i=0; i<n; i++) {
  for(j=0; j<n; j++) { 
  }
}

빅오표기법을 따르자면, 우리 팀의 문제풀이는 이중 반복문을 사용했기 때문에 O(n^2)의 시간 복잡도를 갖는다. 시간 내에 이중 반복문을 사용하지 않는 풀이는 생각해내지 못했지만, 팀원분께서 O(n)의 시간복잡도를 갖는 해결 방법을 공유해주셨다. 다음부터는 시간복잡도까지 고려해 문제를 풀기 위해 남겨놓는다.

const container = {};
for (let i=0; i<nums.length; i++) {
  const another = target - nums[i];
  if (another in container) {
	return [container[another], i];
  }
  container[nums[i]] = i;
}