[Day 1] 더한값이 특정 수가 나오는 배열의 두 인자 인덱스 구하기

📅 2022.10.04
📖 파트너 : 모유진

문제설명 :
twoSum함수에 숫자배열과 '특정 수'를 인자로 넘기면,
더해서 '특정 수'가 나오는 index를 배열에 담아 return해 주세요.
가정 :
target으로 보내는 합계의 조합은 배열 전체 중에 2개 밖에 없다고 가정하겠습니다.

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

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

nums[0] + nums[1] = 4 + 9 = 13 이다

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

1. 이중포문을 이용한 풀이

처음에는 nums 배열을 두번 탐색해 각각의 엘리먼트를 더했을때 target값이 나오는 조건을 충족하는 nums배열의 값을 구하도록 이중포문으로 풀어야 겠다고 생각했다

const twoSum = (nums, target) => {

  let result = [];
  for (let i = 0; i < nums.length; i++) {
    for (let j = 0; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        result.push(i);
        result.push(j);
      }
    }
  }
  return result;
}

인덱스 값을 넣어줄 빈 배열을 선언하고 포문을 돌며 조건을 만족하는 엘리먼트의 인덱스 값을 .push 메서드를 이용해 뒤에서부터 넣어준다.
i는 0 일때 j는 0부터 마지막 배열까지 순회하고 i값이 순차적으로 증가되므로 반환되는 인덱스 값의 첫번째 값으로 i를 반환하고 두번째 값으로 j를 반환해야한다.
nums 배열의 순서대로 만족하는 값을 반환해야되기 때문

---

2. sort와 while문을 이용한 풀이

풀고 나서 이중포문의 시간복잡도가 높기 때문에 더 간결한 풀이가 있을지 생각해 보았다.

처음에는 막연히 while문을 사용해서 변수 두개i,j를 각각 nums 배열의 첫번째 인덱스값0, nums 배열의 마지막 인덱스 값nums.length-1으로 지정해 놓고 while문 안에서 i부터 j까지 각각 순회시켜야 겠다고 생각했다

조건을 만족하면 i와 j를 반환하는 방법을 생각했는데, i 와 j가 각각 증가하고 감소하는 조건을 따로 지정해 주어야해서 특정한 배열에서만 적용이 가능했다 (오름차순이거나 내림차순일 조건일때만)

그렇게 되면 오름차순 또는 내림차순으로 정렬하기전 배열의 엘리먼트값을 저장을 미리 해놓고 정렬된 배열의 조건을 만족하는 값을 반환 받아 그 값으로 미리 저장해둔 초기의 배열에서 indexOf()로 구해야 겠다고 생각했다

const twoSum = (nums, target) => {
  const newNums = [];
  for (let i = 0; i < nums.length; i++) {
    newNums.push(nums[i]);
  }
  //nums.sort();
  nums.sort((a, b) => b - a);
  let i = 0;
  let j = nums.length - 1;
  let result = [];

  while (i < j) {
    if (nums[i] + nums[j] === target) {
      result.push(nums[i]);
      result.push(nums[j]);
      break;
    } else if (nums[i] + nums[j] > target) {
      i += 1;
    } else {
      j -= 1;
    }
  }
  let num1 = newNums.indexOf(result[0]);
  let num2 = newNums.indexOf(result[1]);
  return [num1, num2].sort();
};

이 코드를 짤 때 유의해야 할 점은

• while문의 조건을 만족했을때 break메서드나 return 메서드를 이용하여 while문을 빠져 나와야 result array변수에 제대로 값이 담긴다
• 처음 매개변수로 받은 nums 배열은 const newNums = nums로 바로 담으면 안된다. 이 후에 sort() 메서드로 nums 배열의 순서가 바뀌는데 바뀐값이 newNums에 바로 적용되기 때문에 for문을 이용해 하나씩 배열에 담아 반환 해야 한다.
• nums로 받아오는 배열에 음수가 있을 경우도 생각하여 단순히 nums.sort()를 할 것이 아니라 nums.sort((a, b) => b - a) 를 사용해 음수인 배열값도 적용 되도록 해주어야한다
  처음에 이것 때문에 3문제중 2문제만 맞다고 뜨게 됨

---

3. 객체의 key, value 를 이용한 풀이

두번째 풀이에서 다른방식으로 풀기 위해 너무 억지스럽게 풀었다는 생각이 들었다.
그래서 구글링을 해 본 결과 객체를 이용해서 풀 수 있다는 소스를 얻어서 풀어보았다.

두번째 풀이에서와 마찬가지로 처음 nums 배열의 인덱스를 저장 해준다는 점은 같았다.

다만 객체를 이용해 좀 더 직관적으로 object[key]=value 형태로 풀 수 있다는 점과 target값에서 nums 엘리먼트 하나를 뺀 값이 내가 구해야 하는 값으로 푼다는 방식은 조금 달랐는데, 이렇게 해줌으로써 for문을 하나만 사용해도 풀이가 가능해졌다.

const twoSum = (nums, target) => {
  const map = {};

  for (let i = 0; i < nums.length; i++) {
    const another = target - nums[i];

    if (another in map) {
      return [map[another], i];
    }

    map[nums[i]] = i;
  }

  return null;
};

이 코드를 짤 때 유의해야 할 점은

• 먼저 빈 객체 변수를 생성한다
• 새로운 another 변수에 target - nums[i] 값을 그때 그때 넣어가면서 조건문을 만족하는지 확인하고 만족하지 못하면 map객체에 값을 담는다
• 객체에 key 값을 nums[i]로 하고 value 값을 인덱스 넘버인 i로 담아준다 객체의 값을 업데이트후 i값이 증가하게된다
• 다시 수행된 반복문에서 조건인 객체 map 안에 another 변수의 값이 있다면 인덱스번호를 배열에 담아 리턴하는데 순서가 [map[another], i]로 리턴된다
• 처음에는 i=0부터 시작하므로 리턴도 [i, map[another]] 순서로 반환해야한다고 생각했다. 하지만 for문을 차근차근 따라가보며 변수를 테스트 해보면 쉽게 이해가 된다

만약 nums=[5, 3, 6, 1] 이고 target=8 이라면
i=0 일때 another = 8 - 5 = 3
	map = {} >> if문 false
    map = {5:0} 저장
i=1 일때 another = 8 - 3 = 5
    map = {5:0} 으로 another5가 map 객체 키값으로 존재
    return [0, 1] 되어야 하므로 [map[another], i]순서로 반환되어야 한다