[알고리즘] 문제 해결 패턴 (1) 빈도수 세기

빈도수 세기 패턴

객체나 Set을 활용하여 값의 빈도나 횟수를 저장하는 방식

이렇게 하면 중첩 반복문 없이도 시간 복잡도 O(N^2)를 피할 수 있다.

 

문제 

두 개의 배열을 입력받는 same이라는 함수를 작성

이 함수는 첫 번째 배열의 각 값이 두 번째 배열에서 제곱된 값으로 존재하는 경우에 true를 반환해야 합니다.

값의 빈도도 동일해야 합니다.

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)

내가 풀은 방법

function same(arr1, arr2) {
  // 배열 오름차순 정렬
  arr1.sort((a, b) => a - b);
  arr2.sort((a, b) => a - b);

  // 길이가 다르면 false
  if (arr1.length !== arr2.length) return false;

  // arr1의 각 값을 제곱해서 arr2와 비교
  for (let i = 0; i < arr1.length; i++) {
    if (arr1[i] ** 2 !== arr2[i]) {
      return false;
    }
  }
  return true;
}

console.log(same([1, 2, 3], [1, 4, 9])); // true
console.log(same([1, 2, 1], [1, 4, 4])); // false
console.log(same([1, 2, 2], [1, 4, 4])); // true

 

영상 속 해결방법(1)

function same(arr1, arr2) {
  // 두 배열의 길이가 다른지 여부에 대한 확인
  if (arr1.length !== arr2.length) {
    return false;
  }

  for (let i = 0; i < arr1.length; i++) {
    // 각 제곱을 전달하는 위치에 indexOf를 호출
    let correctIndex = arr2.indexOf(arr1[i] ** 2);
    if (correctIndex == -1) {
      return false;
    }
    console.log(arr2);
    arr2.splice(correctIndex, 1);
  }

  return true;
}

이러한 접근법은 O(n²), 시간이 사용된다. 

1. 첫번째  for문에서 두 배열의 길이가 다른지에 대한 여부를 즉시 확인 가능
   • arr1, arr2의 값이 다르면 참이 될 수 없다. 
   • 즉, 작동하지 않는다.
2. indexOf를 작성한 이유는 각 값의 제곱을 전달하기 위해서이다. 
3.  
4. correctIndex가 -1인지 확인하고 그렇지 않은 경우 거짓 반환
   • 즉, 대응하는 값이 없다는 의미

indexOf의 기능은 전체 배열을 반복하거나 중첩된 루프인 전체 배열을 잠재적으로 반복한다. 

따라서 n이 배열의 길이를 늘리면 이 값이 이와 값이 이와 같이 증가하여 2차 관계로 중첩된다.

 

👆🏻 indexOf 설명 

indexOf는 배열이나 문자열에서 특정 값이 어디에 있는지 찾아주는 도구

JavaScript에서 배열이나 문자열에 기본으로 제공되는 메서드인데, "이 값이 있으면 그 위치를 알려주고, 없으면 -1을 알려줘"라는 역할을 한다.

 

배열

let arr = ["사과", "바나나", "오렌지"];
console.log(arr.indexOf("바나나")); // 1 (바나나는 1번 위치에 있음)
console.log(arr.indexOf("포도"));   // -1 (포도는 없음)

 

문자열

let str = "안녕하세요";
console.log(str.indexOf("녕")); // 1 (녕은 1번 위치에 있음)
console.log(str.indexOf("ㅋ")); // -1 (ㅋ은 없음)

 

• 위치 번호는 0부터 시작. 첫 번째가 0, 두 번째가 1, 이런 식으로!
• 찾으려는 값이 여러 개 있으면 가장 먼저 나온 위치만 알려준다.
• 값이 존재하는지 확인

👆🏻 splice 설명 

splice는 배열에서 요소를 추가하거나 제거할 때 사용하는 메서드

• 사용법: array.splice(시작_인덱스, 제거할_개수, [추가할_요소들])
  • 예: let arr = [1, 2, 3]; arr.splice(1, 1); → [1, 3] (인덱스 1의 요소 2를 제거)

여기서는 arr2.splice(correctIndex, 1)로, arr2에서 correctIndex 위치의 요소 1개를 제거

 

영상 속 코드에서 spliec를 사용한 이유는 빈도수(횟수)를 맞추기 위해 사용

ㄴsplice는 arr1의 현재 값(arr1[i])의 제곱값에 해당하는 arr2의 숫자를 찾아서 지웁

 

 

리팩토링

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        
    }
    for(let key in frequencyCounter1){
        if(!(key ** 2 in frequencyCounter2)){
            return false
        }
        if(frequencyCounter2[key ** 2] !== frequencyCounter1[key]){
            return false
        }
    }
    return true
}
}

 

첫번째 배열에 루프를 적용하여 두 번째 배열의 하위 후프에서 각 값을 확인하는 대신

각 배열에 한번씩 개별적으로 루프를 적용할 수 있다. (첫번째 for문과 두번째 for문 처럼)

두개의 루프가 두개의 중첩된 개별 루프보다 훨씬 낫다.

이러한 시간 접근법은 O(n)이다. 

 

✅ 빈도수 세기 패턴의 개념은 보통 객체를 사용한다는 것

• 객체를 사용해 프로파일을 구성하는것은 배열이나 문자열의 내용을 분석하는 방법
• 보통 배열이나 문자열과 같은 선형 구조를 구성하는 것
• 그러면 해당 분석을 문자열이나 배열에서 생성된 다른 객체의 형태와 신속하게 비교가능

✅  따라서 두 개의 배열을 객체로 세분화하여 각 배열의 요소들을 분류한 다음 각 배열을 비교가능하다. 

---

애나그램

내가 작성한 코드

function validAnagram(str1, str2){
// str1, str2의 배열을 오름차순으로 정렬
str1 = str1.split('').sort().join('')
str2 = str2.split('').sort().join('')

// str1과 str2의 길이 같지 않으면 false로 return한다.
  if(str1.length !== str2.length) return false;
  
  // str1의 원소만큼 순회를 하다가
  for(let i = 0; i < str1.length; i++) {
  // str1의 원소와 str2의 원소가 같지 않으면 false로 return한다.
      if(str1[i]!==str2[i]) {
          return false;
      }
  }
  // 모든 문자가 다 일치하면 true 반환
  return true;
}

str1, str2의 배열을 오름차순으로 정렬한다. 

영상에 나온 코드

• 루프를 적용해 만든 객체를 사용하고 중첩되지 않은 두 번째 루프를 사용해야한다.

function validAnagram(first, second) {
  if (first.length !== second.length) {
    return false[i];
  }

  const lookup = {};

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

  for (let i = 0; i < second.length; i++) {
    let letter = first[i];

    if (!lookup[letter]) {
      return false;
    } else {
      lookup[letter] -= -1;
    }
  }
}

 

 

애너그램 판별 방식 여러 개의 데이터가 서로 같은 구성 요소를 가지고 있는지 비교해야 하는 다양한 상황에서 활용된다.

• 배열이 같은 요소들로 이루어졌는지 판별
  → 두 배열이 같은 개별 데이터 조각으로 구성되어 있는지 확인할 때
• 한 배열이 다른 배열의 요소를 제곱한 값들로 구성되었는지 판별
  → 예: [1, 2, 3]과 [1, 4, 9] (각 요소를 제곱한 값인지 확인)
• 같은 숫자로 이루어졌지만 순서만 다른 배열 판별
  → 예: [3, 1, 2]와 [1, 2, 3] (같은 숫자로 구성되었는지 확인)