[알고리즘] frequency counter pattern

부트캠프에서 매일 아침 알고리즘 문제를 하루에 한 문제씩 풀게 한다. 오늘의 문제는 다음과 같았다. 

💡 문자열을 입력받아 아이소그램인지 여부를 리턴한다. 아이소그램(isogram)이란 각 알파벳을 한 번씩만 이용해서 만든 단어나 문구를 말한다. 

 

처음에 문제를 보고는 별 생각 없이 다음과 같이 이중 for문으로 풀었다.

function isIsogram(str) {
  // 빈 문자열이 들어오면 true를 출력한다는 주의사항을 반영
  if (!str) return true;

  str = str.toLowerCase();

  for (let i = 0; i < str.length; i++) {
    for (let j = i + 1; j < str.length; j++) {
      if (str[i] === str[j]) return false
    }
  }
  return true;
}

 

문제는 바로 지난 주말 Udemy 자료구조&알고리즘 강의에서 빈도수 세기 패턴을 수강했다는 사실이다. 며칠 전 배운 건 새까맣게 까먹고 레퍼런스 코드를 보고나서야, 아 이럴 때 쓰는거구나! 알았지 뭐야 😇 

그래서 바로 아래와 같이 코드를 수정해서 문제를 다시 풀어봤다. 

 

function isIsogram(str) {
  if (!str) return true;

  str = str.toLowerCase();
  let obj = {}

  for (let i = 0; i < str.length; i++) {
  	// in 연산자로 obj 안에 str[i] 라는 key가 있는지 확인
    if (str[i] in obj) return false
    
    // str[i]라는 key가 없다면 해당 key를 obj 안에 넣어준다. 
    obj[str[i]] = 1;
  }
  
  return true;
}

 

이 문제는 같은 문자가 있느냐 없느냐만 확인해서 그 여부에 따라 true / false 만 반환해주면 되는 문제였기에 key-value 쌍에서 value를 뭘로 지정해 줘도 상관없다. 다시 말해 'present' 라는 문자열을 넣어도 되고, 1이 아닌 다른 숫자나 boolean 값을 넣어도 괜찮다. 

 

복잡한 문제가 아니기에 이중 for문으로 푸는 게 더 간단해 보일 수도 있지만 for loop가 중첩되면 시간 복잡도 측면에서 O(n^2)이 되기 때문에 str의 길이가 무한정 늘어난다고 가정하면 시간이 제곱으로 늘어나게 된다. 하지만 객체를 사용해서 for loop를 한 번만 사용하는 경우 시간 복잡도가 O(n)으로 줄어들게 된다. 

 

 

📍 frequency counter 패턴의 핵심 :

1) 문자열이나 배열 같은 선형 구조를 분석해서 

2) 해당 문자열이나 배열을 객체를 사용해 해체하여 분류한 다음,

3) 객체를 확인(또는 문제에 따라 비교)하면

코드를 크게 향상시킬 수 있다.