[JS] 이중 반복문 성능 개선 방법

function checkSame(arr1, arr2) {
  let counter1 = {};
  let counter2 = {};
    
  for (let item of arr1) {
    counter1[item] = (counter1[item] || 0) + 1;
  }
    
  for (let item of arr2) {
    counter2[item] = (counter2[item] || 0) + 1;
  }

  for (let key in counter1) {
    if (!(key in counter2)) {
      return false;
    }
    if (counter2[key] !== counter1[key]) {
      return false;
    }
  }
  return true;
}

console.log(checkSame([3, 5, 7, 8, 9], [3, 7, 9, 8, 5])); // true
console.log(checkSame([1, 2, 3, 4], [4, 3, 2, 1])); // true
console.log(checkSame([1, 2, 3, 4], [4, 3, 2, 1, 1])); // false

 

이중 반복문의 성능 개선을 위한 코드이다. 위와 같은 코드를 사용하면 이중 반복문 사용 시 예를 들어 10000번 * 10000번 = 100000000번 반복할 코드를 10000번 + 10000번 = 20000번만 코드를 돌려 결과를 출력해낼 수 있다. 

 

변수 counter1 과 counter2에 각각 빈 객체를 할당하고, 반복문을 사용해 arr1의 배열을 item으로 차례로 할당하면서 해당 item이 counter1 객체에 들어있는지 확인한다. 만약 등록되어있지 않다면, 새로운 키 'item'을 counter1 객체에 추가하고 그 값을 1로 초기화한다.

 

만약 arr1 에 들어온 값이 ['a', 'b', 'a'] 라면 counter1['a']  => { a :   }의 형태가 되고 우변의 괄호 안의 식인 counter1['a'] || 0 이 실행된다. 이때 a 에는 value 값이 없으므로 or 연산자에 의해 0이 되고 괄호 밖에 있는 + 1 에 의해 { a : 1 } 의 형태가 된다 

마찬가지로 conuter1['b'] => { b :  }의 형태가 되고 우변의 counter['b'] || 0 의 식이 실행된다. 이때 b에도 value 값이 없으므로 or 연산자에 의해 0이 되고 괄호 밖 +1에 의해 { b : 1 } 의 형태가 된다.

마지막으로 counter1['a'] 가 들어오게 되면 우변의 식 counter1[ 'a' ]는 => { a : 1 } 의 값이 이미 counter1 안에 있다. 

따라서 counter1['a'] 는 true이기 때문에 괄호 안 논리연산자의 결과는 1이 되고 괄호 밖 + 1 에 의해 2가 된다. 

추가적으로 만약 counter1 객체 안에 { a : 10 } 이라는 값이 이미 존재하고 또 다시 a가 item으로 들어오게 된다면 

우변의 counter['a'] 는 { a : 10 } 즉 , 10을 의미하므로 10 + 1 = 11이 된다. 

이와 같은 원리로 두 배열의 중복 요소를 카운트하는 것이다. 

 

여기까지 진행된 후 counter1 = { '3' : 1, '5' : 1, '7' : 1, '8' : 1, '9' : 1 }   

                             counter2 = { '3' : 1, '5' : 1, '7' : 1, '8' : 1, '9' : 1 }   가 된다. 

for (let key in counter1) {
    if (!(key in counter2)) {
      return false;
    }

그 후 이러한 코드가 나오는데 counter1에서 key라는 변수로 값을 넘겨받아 만약 counter2에서 값을 넘겨받은 key와 비교했을 때 

다르다면 false를 리턴한다. 이때 key 값을 console을 찍어보게 되면 3, 5, 7, 8, 9 가 나오게 된다. 즉, key 값만 넘겨받은 것이다.

 

if (counter2[key] !== counter1[key]) {
      return false;
    }

 또한번의 조건문을 활용해서 비교하게 되는데 이땐 counter2[key] 즉, value 값을 불러와서 비교하는 것이다. 

console을 찍어보면 1, 1, 1, 1, 1 이 나오게 된다. 

 

모두 통과하게되면 true를 리턴하게 된다. 

 

---

function sameString(first, second) {
  if (first.length !== second.length) {
    return false;
  }

  const lookup = {};

  for (let i = 0; i < first.length; i++) {
    let letter = first[i];
    lookup[letter] ? (lookup[letter] += 1) : (lookup[letter] = 1);
  }

  for (let i = 0; i < second.length; i++) {
    let letter = second[i];
    if (!lookup[letter]) {
      return false;   
    } else {
      lookup[letter] -= 1;
    }
  }

  return true;
}

console.log(sameString("anagram", "nagaram"));

먼저 이 코드는 하나의 변수에만 객체를 할당해서 문제를 해결하는 코드이다. 

1차적으로 각 매개변수의 길이를 확인하여 일치여부를 확인한다. 그 후 반복문을 돌면서 letter에 a n a g r a m 이 차례로 할당된다.

lookup[a] ? (lookup[a] += 1) : (lookup[a] = 1) 

이 식은 lookup[a]가 true 라면 (lookup[a] += 1) 실행, 값이 없다면 (lookup[a] = 1)이 실행된다. 

만약 a가 처음 들어가게 되면 lookup[a]는 값이 없으므로 (lookup[a] = 1)이 실행된다. 

그 후 a가 다시 들어가게 되면 lookup[a]은 true가 되므로  + 1이 된다. 이러한 원리로 카운트가 진행된다. 

 

두번째 반복문에서는 변수 letter에 second[i]가 들어가게 된다. 그 후 조건문을 활용하여 lookup[letter] 이 false 라면 false를 리턴하고 조건에 충족하면 true를 리턴한다.