빈도수 세기 패턴(객체를 활용한 카운팅)

빈도수를 세야하는 경우 객체를 활용하면 편리하다.

- 문자열과 배열을 반복시킬 때는 for~ of,

객체의 속성을 반복시킬 때는 for ~ in 을 사용함에 주의할 것.

 

빈도수 세기- 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(str1, str2){
    const firstStrObj = {};
    const secondStrObj = {};
    console.log("str1 : ", str1)
    console.log("str2 : ", str2)
    if( str1.length !== str2.length) return false;
    
    
    // 객체 1에 담기
    for(let char of str1) {
        firstStrObj[char] = (firstStrObj[char] || 0) + 1;
    }
    
    // 객체2에 담기
    for(let char of str2) {
        secondStrObj[char] = (secondStrObj[char] || 0) + 1;
    }
    
    console.log( JSON.stringify(firstStrObj));
    console.log( JSON.stringify(secondStrObj));
    
    // 객체 1의 속성을 꺼내면서 객체2와 비교 
    for(let key in firstStrObj) {
        if (firstStrObj[key] !== secondStrObj[key] ) return false;
    }
    
    return true;
    
}

validAnagram("cinema", "iceman")
/*
str1 :  cinema
str2 :  iceman
{"c":1,"i":1,"n":1,"e":1,"m":1,"a":1}
{"i":1,"c":1,"e":1,"m":1,"a":1,"n":1}
*/

 

아래는 두 번 만 순회한다. 이게 더 좋은 방식이다.

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];
    // if letter exists, increment, otherwise set to 1
    lookup[letter] ? lookup[letter] += 1 : lookup[letter] = 1;
  }
  console.log(lookup)

  for (let i = 0; i < second.length; i++) {
    let letter = second[i];
    // can't find letter or letter is zero then it's not an anagram
    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) 

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



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

Time: O(N)

예시 인풋:

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

 

숫자 연산과 객체를 사용하여 해결하고 싶었으므로 아래와 같은 방법으로 해결하였다.

function sameFrequency(num1, num2){
    const numObj = {};
    
    let digitOne = Math.trunc(Math.log10(num1))
    let digitTwo = Math.trunc(Math.log10(num2))
    if(digitOne !== digitTwo) return false;
    
    for( let i = 0; i <= digitOne; i++) {
        let r1 = num1 % 10;
        numObj["num1"] = (numObj["num1"] + r1 || r1);
        num1 = Math.trunc(num1/10);
        
        let r2 = num2 % 10;
        numObj["num2"] = (numObj["num2"] +r2 || r2);
        num2 = Math.trunc(num2/10);
    }
    
    return numObj.num1 === numObj.num2;
}

/*
// 원래는 아래와 같이 작성했음. 
// 매 실행마다 초기화되어야 하는데, 오브젝트를 바깥에 선언하는 바람에 이전 실행값이 남아있었음
const numObj = {
   
}
function sameFrequency(num1, num2){
   
   
   let digitOne = Math.trunc(Math.log10(num1))
   let digitTwo = Math.trunc(Math.log10(num2))
   if(digitOne !== digitTwo) return false;
   
   
   for( let i = 0; i <= digitOne; i++) {
       let r1 = num1 % 10;
       numObj["num1"] = (numObj["num1"] + r1 || r1);
       num1 = Math.trunc(num1/10);
       console.log(num1)
       
       let r2 = num2 % 10;
       numObj["num2"] = (numObj["num2"] +r2 || r2);
       num2 = Math.trunc(num2/10);
   }
   
   console.log(JSON.stringify(numObj))

   console.log(numObj.num1 === numObj.num2) 
   
}
/*

 

로직에는 문제 없어보였는데 계속해서 값이 틀리는 문제가 발생했다.  빈도를 카운트 할 오브젝트를 함수의 바깥에 선언한 것이 원인이었다.  프로그래머스 사이트는 매 테스트마다 함수의 인스턴스를 신규 생성하여 진행한다. 반면 유데미의 경우 한 번 생성한 함수 인스턴스를 여러 번 사용한다. 따라서 오브젝트의 속성이 매번 초기화 되지 않으므로, 다음 테스트에서 이전 테스트가 남긴 값을 참조하게 된 것이었다. 즉, 함수 외부의 변수가 상태를 유지(stateful)하게 됨으로써 발생한 문제였다.

 

추후 코드 작성 시 아래의 가이드를 주의할 필요를 느꼈다.

 

• 함수는 '순수 함수'로 작성 (동일 입력 = 동일 출력)
• 상태는 함수 내부에서 관리
• 전역 변수 사용을 최소화

 

객체를 사용하지 않고 수학적 연산만을 사용하려고 한다면 아래와 같은 방법이 더 간편한 듯하다.

function sameFrequency(num1, num2) {
    if(Math.floor(Math.log10(num1)) !== Math.floor(Math.log10(num2))) {
        return false;
    }
    
    const getSum = num => {
        let sum = 0;
        while(num > 0) {
            sum += num % 10;
            num = Math.floor(num/10);
        }
        return sum;
    }
    
    return getSum(num1) === getSum(num2);
}

 

물론 빠른 해결을 위해서라면 아래의 방법을 사용할 것이다.

function sameFrequency(num1, num2) {
    // 숫자를 문자열로 변환
    const str1 = num1.toString();
    const str2 = num2.toString();
    
    // 자릿수가 다르면 바로 false
    if(str1.length !== str2.length) return false;
    
    // 각 자리 숫자의 합 구하기
    const sum1 = str1.split('').reduce((acc, curr) => acc + Number(curr), 0);
    const sum2 = str2.split('').reduce((acc, curr) => acc + Number(curr), 0);
    
    return sum1 === sum2;
}

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