(문제 해결 패턴) 빈도수 찾기 패턴

'어떤 배열 2개를 던져주고 두 배열을 비교해서 어떠한 답을 도출해라'

라는 문제가 나오면 어떻게 해야할까?

 

일단 naive한 답으로써는...

for문을 이중으로 사용하여

for 배열1 {

    for 배열2 {

       배열1의 각 요소와 배열2 모두 비교

    }
}

위와 같은 방식으로 구현하는 것이다. 배열 2개를 모두 순회하여 답을 구할 수 있다.

즉, O(N^2)의 복잡도를 가지게 된다.

 

 

O(N^2)로 아래의 문제를 한번 풀어보도록 하자.

---

문제 원문)

/*
Write a function called same, which accepts two arrays.
The function should return true 
if every value in the array has it's correponding value squared in the second array.
The frequency of values must be the same.
*/


// example
same([1, 2, 3], [4, 1, 9]) // true
same([1, 2, 3], [1, 9]) // false
same([1, 2, 1], [4, 4, 1]) // false (must be same frequency)

문제 번역)

• 2개의 배열을 인수로 갖는 same이라는 함수를 작성해라.
• 첫번째 어레이의 각 엘레멘트를 제곱한 값이 두번째 어레이의 각 엘레멘트와 상응한다면 true를 반환하고
• 그렇지 않다면 false를 반환한다.
• 이때, 각 값의 빈도는 모두 같아야 한다.
  ( 첫번째 배열이 [2, 2, 1] 이라면 두번째 배열은 (순서 상관없이) 4, 4, 1이 있어야만 한다.)

 

풀이 전 생각)

• 문제 이해 : 배열 2개가 주어지는데 첫번째 배열은 두번째 배열의 제곱근이다.
• false 상황 1 : 각 배열의 길이가 맞지 않을 경우, 각 값의 빈도가 다를 것이다.
• false 상황 2 : 첫번째 배열의 엘리먼트를 제곱한 값이 두번째 배열에 없을 경우
• false 상황 3 : 첫번째 배열을 제곱한 값이 두번째 배열에 동일한 빈도수로 존재하지 않을 경우.

---

 

O(N^2) 시간복잡도를 가지는 풀이)

/*

<풀이 전 생각>

1. 인수로 받는 두 어레이의 length가 각각 다를 경우 false
2. for문으로 첫번째 어레이의 엘리먼트를 제곱한 값이 두번째 배열의 엘리먼트와 일치하는지 확인
3. 빈도수가 같은지 확인해야 함.

*/

const same = (arr1, arr2) => {
    if (arr1.length !== arr2.length) return false // (1)
    for (let element of arr1) {
	    let index = arr2.indexOf(element ** 2)    // (2) 
        if (index === -1) {                       // (3)
		return false
        }
    arr2.splice(index, 1)                         // (4)
	}
    return true                                   // (5)
}

/*
  (1) 두 어레이의 길이가 다를 시 false 리턴
  (2) 첫번째 어레이의 엘리멘트를 제곱한 값이 arr2에 있는지, 있다면 그 인덱스를 출력
  (3) indexOf가 -1이면 arr2에 해당하는 엘리멘트가 없다는 것임 = false 리턴 
  (4) 만약 arr2에 있다면, 해당 인덱스의 부분을 삭제시킴
  (5) 모든 순회가 끝났다면 이상이 없다는 의미이므로 true를 반환
*/

• for문 안에 indexOf 메서드가 있어서 O(N^2)이다.
  ( indexOf는 어레이 안에 해당하는 element를 찾기 위해 배열을 모두 순회한다. )
• 모든것들이 무사히 순환되면 이상이 없다는 의미이므로 true를 반환하게 된다.

위의 경우는 O(N^2)의 시간복잡도를 가지게 된다.

---

 

이러한 문제는

객체를 이용한 빈도수 패턴 방법을 이용하게 되면

시간 복잡도를 O(N)으로 줄일 수 있다.

 

오브젝트에서 key를 통해 value를 바로 찾는 것이

배열 내 인덱스를 모조리 뒤지는 것보다 훨씬 빠르기 때문이다.

 

---

반복문 속에 반복문이 있는 것이 아닌

아래와 같이 for문 3개가 병렬로 구조되어있는 상태라면

대략 3N 정도의 시간복잡도에 해당한다.

 

시간복잡도는 간단히 표현되므로 결국 아래의 시간복잡도는

O(N)이 된다. 

 

 

O(N) 시간복잡도를 가지는 풀이)

/*
리팩토링
배열 이중 for문 탐색 -> 빈도수 패턴 찾기

1. 오브젝트에서 key를 통해 value를 찾는 것은 빠르다.
2. 3N, 5N도 결국에는 O(N)값을 가진다.
3. 오브젝트 2개를 비교한다는 것 외에는 위의 조건과 같다.

*/

function same(arr1, arr2) {
    if(arr1.length !== arr2.length) return false // 배열 length가 다르면 false
    let counter1 = {} // 빈 객체1
    let counter2 = {} // 빈 객체2
    for (let val of arr1) {
        counter1[val] = (counter1[val] || 0) + 1  // (1)
    }
    for (let val of arr2) {
        counter2[val] = (counter2[val] || 0) + 1  // (2) 
    }
    for (let key in counter1) { // counter1의 key를 통해 N번 순회함 
        /* if (!(key ** 2 in counter2)) {
            return false // 만약 counter2에 key를 제곱한 값이 없다면? false
        } 그러나 이 코드가 없어도 제대로 동작하긴 함 
        */
        if (counter2[key ** 2] !== counter1[key]) {
            return false  // (3) 
        }
    }
    return true           // (4)
}

/*
  (1) N번 순회) arr1 엘리먼트의 빈도를 카운트 함.
  (2) N번 순회) arr2 엘리먼트의 빈도를 카운트 함.
  (3) 만약 제곱한 값의 빈도가 서로 다르다면? false
  (4) 모든 순회가 이상이 없었다면 true
*/

 

 

새로 배운 메서드 / 키워드

• Array.indexOf(value) : value가 Array 내에 존재한다면 그 인덱스를 반환, 없다면 -1을 반환. O(N)에 해당
• for 엘리먼트 of 배열 : 배열 내 엘리먼트를 바로 찍어서 순환해주는 상냥한 for문. O(N)에 해당 
• for 엘리먼트 in 객체 : 객체 내 key를 찍어서 순환해주는 상냥한 객체 전용 for문. O(N)에 해당