[알고리즘JS] 빈도 수 세기 패턴

🤖 문제 해결 패턴

---

문제 해결 패턴에서 빈도 수 세기 패턴을 정리해보자! 사실 코드를 치며 각 주제마다 폴더를 만들어 README에 정리를 한 내용을 슬쩍슬쩍 옮겨오는 것이지만! 블로그에도 정리해두면 좋을 것 같아서 옮겨본다.

레츠꼬우~!_!

 

 

🐣 Question

---

2개의 배열을 허용하는 same이라는 함수를 작성.
배열의 모든 값이 두 번째 배열에 해당하는 값을 가지면 참을 반환.
따라서 첫 번째 배열에는 여러 값, 두 번째 배열의 값이 정확히 동일하지만 제곱되어 있음.
순서는 상관 없고, 제곱만 되어 있으면 됨. 값의 빈도도 동일해야 함.

🐤 example

입력 값

1,2,3

반환 값

4,1,9 // true
1,9,9 // false

🐤 solution 1

• O(o^2)

function same(arr1, arr2) {
  if (arr1.length !== arr2.length) {
    return false;
  }
  for (let i = 0; i < arr1.length; i++) {
    let correctIndex = arr2.indexOf(arr1[i] ** 2)
    if (correctIndex === -1) {
      return false;
    }
    console.log(arr2);
    arr2.splice(correctIndex, 1)
  }
  return true;
}

same([1, 2, 3, 2], [9, 1, 4, 4])

 

설명

중첩된 루프 사용. 하나의 루프 작성하지만 그 자체가 루프인 인덱스 사용.

1. 두 배열의 길이가 다른지 여부 확인
2. 각 값의 제곱을 전달하는 위치에 indexOf를 호출(해당 배열에 루프 적용)
   indexOf
3. arr2에서 arr1의 각 값에 해당하는 인덱스를 물음
   (ex [1,2,3], [9,1,4] 일경우, arr2에서 arr1의 값 1의 제곱이 어느 인덱스인지)
4. -1 값일 경우 false; 처리. 나머지 corrrectIndex 저장
5. splice 사용하여 true값들인 correctIndex 배열에서 제거
   splice

아래 흐름대로 감

[9,1,4,4]
[9,4,4]
[9,4]
[4]
true

 

특징

• O(o^2) : 배열 길이 1000이면 100만번반복
• 제곱 시간 사용. 순진한 접근법
• indexOf 기능 전체 배열 반복, 중첩된 루프인 전체 배열 잠재적 반복
• 따라서 n이 배열의 길이를 늘리면 이 값이 함께 증가하여 2차 관계로 중첩

 

🐤 solution 2

• O(n)

function same(arr1, arr2) {
  if (arr1.length !== arr2.length) {
    return false;
  }
  let frequencyCounter1 = {}
  let frequencyCounter2 = {}
  for (let val of arr1) {
    frequencyCounter1[val] = (frequencyCounter1[val] || 0) + 1
  }
  for (let val of arr2) {
    frequencyCounter2[val] = (frequencyCounter2[val] || 0) + 1
  }
  console.log(frequencyCounter1);
  console.log(frequencyCounter2);
  for (let key in frequencyCounter1) {
    if (!(key ** 2 in frequencyCounter2)) {
      return false
    }
    if (frequencyCounter2[key ** 2] !== frequencyCounter1[key]) {
      return false
    }
  }
  return true
}

same([1, 2, 3, 2, 5], [9, 1, 4, 4, 11])

 

설명

1. 배열 길이 비교
2. for of 로 각 배열 돌려줌
3. frequencyCounter1 혹은 2 객체에 각 배열(arr1,arr2) 값들이 있으면 넣어주고 아니면 +1

   {1: 1, 2: 2, 3: 1, 5: 1}
   {9: 1, 1: 1, 4: 2, 11: 1}

4. for in 로 frequencyCounter1 객체 돌려주면서 값들 있는지 확인
   frequencyCounter2랑 key값 다르면 false(ex: arr1의 key 2를 2배한 4가 arr2 key에 있는지 확인)
5. 두번째 if문에서 key 빈도수 확인(key의 value 비교)

특징

• O(n) (여기서는 3n정도 O(n))
• 첫 번째 배열에 루프를 적용하여 두 번째 배열의 하위 루프에서 각 값을 확인하는 대신 각 배열에 한 번씩 개별적으로 루프를 적용
• 두 개의 루프가 두 개의 중첩된 개별 루프보다 훨씬 나음
• 각 배열에 한 번씩 개별적으로 루프를 적용

{1:1, 2:2, 3:1}
{1:1, 4:2, 9:1}
true

{1:1, 2:2, 3:1,5:1}
{1:1, 4:2, 9:1, 11:1}
false

 

🐣 빈도수 세기 - validAnagram

---

문제

두 개의 문자열이 주어졌을 때, 두 번째 문자열이 첫 번째 문자열의 애너그램인지 확인하는 함수를 작성합니다. 애너그램은 다른 글자의 글자를 재배열하여 형성된 단어, 구 또는 이름입니다. (예시: cinema -> iceman)

예시:

validAnagram('', '') // true
validAnagram('aaz', 'zza') // false
validAnagram('anagram', 'nagaram') // true
validAnagram("rat","car") // false // false
validAnagram('awesome', 'awesom') // false
validAnagram('amanaplanacanalpanama', 'acanalmanplanpamana') // false
validAnagram('qwerty', 'qeywrt') // true
validAnagram('texttwisttime', 'timetwisttext') // true

안내: 문자열에 소문자만 포함되어 있다고 가정해도 됩니다.
Time Complexity - O(n)

function validAnagram(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;
  }
  console.log(lookup)

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

  return true;
}

// {a: 0, n: 0, g: 0, r: 0, m: 0,s:1}
validAnagram('anagrams', 'nagaramm')

설명

1. 각 문자 길이 확인
2. 첫번째 문자 for 반복 돌리면서 letter에 문자 차례로 넣어줌
3. lookup 배열에 letter key 있으면 +1 해주고, 아니면 1
4. 다음 두번째 문자 for문 반복 letter에 문자 차례로 넣기
5. lookup에 두번째문자의 letter이 없으면 false
6. 있으면 1빼기
7. 입력값 validAnagram('anagrams', 'nagaramm')의 경우 s가 1개 남기 때문에 false임(5번에서 false 됨)

 

 

🤖 Quiz

---

문제1

빈도수 세기 - sameFrequency
sameFrequency라는 함수를 작성하세요. 두 개의 양의 정수가 주어졌을 때, 두 숫자의 자릿수가 같은 빈도를 갖는지 구합니다.



여러분의 솔루션은 반드시 다음과 같은 복잡성을 가져야 합니다.:

Time: O(N)

예시 인풋:

sameFrequency(182,281) // true
sameFrequency(34,14) // false
sameFrequency(3589578, 5879385) // true
sameFrequency(22,222) // false

정답1

풀은 것

function sameFrequency(a, b) {
  const aa = a.toString();
  const bb = b.toString();
  if (aa.length !== bb.length) {
    return false;
  }

  const match = {};
  for (let i = 0; i < aa.length; i++) {
    let letter = aa[i];
    match[letter] = (match[letter] || 0) + 1
  }

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

정답2

function sameFrequency(num1, num2) {
  let strNum1 = num1.toString();
  let strNum2 = num2.toString();
  if (strNum1.length !== strNum2.length) return false;

  let countNum1 = {};
  let countNum2 = {};

  for (let i = 0; i < strNum1.length; i++) {
    countNum1[strNum1[i]] = (countNum1[strNum1[i]] || 0) + 1
  }

  for (let j = 0; j < strNum1.length; j++) {
    countNum2[strNum2[j]] = (countNum2[strNum2[j]] || 0) + 1
  }

  for (let key in countNum1) {
    if (countNum1[key] !== countNum2[key]) return false;
  }

  return true;
}

 

---

밀린 알고리즘 공부 부랴부랴~

 

[알고리즘 JS] 다중 포인터 패턴