[알고리즘/자바스크립트] 알파벳 개수 세고 정렬하기 (Character Frequency)

[문제] Write a function that takes as its input a string and returns an array of arrays as shown below sorted in descending order by frequency and then by ascending order by character.

 

[Example]

characterFrequency('mississippi') === [['i', 4], ['s', 4], ['p', 2], ['m', 1]]

characterFrequency('miaaiaaippi') === [['a', 4], ['i', 4], ['p', 2], ['m', 1]]

 

 

---

 

 

영어 문장을 파라미터로 받아서 각 알파벳의 개수를 카운트하고 위 예시와 같은 2차 배열로 리턴한다. 배열의 순서는 개수가 많은 순서대로 정렬하고 개수가 같은 요소가 있다면 알파벳 순서로 정렬한다.

 

 

내가 생각한 방법은 다음과 같다. (loop이 3번이나 있어서 마음에 안들긴한데...ㅜ)

 

 

1. 먼저 string을 잘게 쪼개서 배열의 형태로 만든다.

2. 배열을 순회하며 개수를 카운트하여 객체 형태로 만든다.

3. 객체의 키값을 배열로 만든 다음 sort 함수를 이용하여 개수 순 -> 알파벳 순으로 정렬한다.

4. 키 배열에 다시 loop을 돌려서 2차 배열의 형태로 만든다.

 

function characterFrequency (string) {
  var strings = string.split('');

  var count = strings.reduce(function (chars, cur, i, arr) {
    if (chars[cur]) {
      chars[cur] += 1;
    } else {
      chars[cur] = 1;
    }
    return chars;
  }, {});

  var keys = Object.keys(count);
  var sorted = keys.sort(function (l, r) {
    if (count[l] > count[r]) {
      return -1;
    } else if (count[l] < count[r]) {
      return 1;
    } else {
      if (l > r) {
        return 1;
      } else {
        return -1;
      }
    }
  });

  var result = [];
  sorted.forEach(function (k) {
    result.push([k, count[k]]);
  });
  return result;
}

 

개수를 카운트할때, 배열의 형태로 만들면서 카운트하는 방법을 생각해봐야겠다.

배열을 객체로 -> 객체에서 다시 배열로 만드는게 너무 복잡한 것 같다.

 

 

---

 

function characterFrequency (string) {
  var strings = string.split('');

  var char = {};
  var i = 0;
  var count = strings.reduce(function (arr, cur) {
    if (arr[char[cur]]) {
      arr[char[cur]][1] += 1;
    } else {
      char[cur] = i;
      arr[i] = [cur, 1];
      i++;
    }
    return arr;
  }, []);

  return count.sort(function (l, r) {
    if (l[1] > r[1]) {
      return -1;
    } else if (l[1] < r[1]) {
      return 1;
    } else {
      if (l[0] > r[0]) {
        return 1;
      } else {
        return -1;
      }
    }
  });
}

 

위에서 언급한대로 위 방법은 쓸데없이 객체 형태로 만들어서 거기서 key값만 따로 배열을 만들어 정렬하고

또 정렬된 배열을 기준으로 배열을 만드느라 loop을 3번이나 돌아야한다.

 

맘에 안들어서 문자의 개수를 셀 때 객체를 만들지 않고 배열로 만드는 방법을 생각해보았다.

 

1. 일단 char이란 이름의 객체를 만들고, i변수를 만든다.

2. strings을 배열로 만들어 loop을 도는데, 개수를 세서 값을 누적할 배열을 초기값으로 넣는다.

3. loop을 돌때 현재 문자열이 char 객체의 key값으로 있는지 확인한다.

 

4. 처음에는 빈 객체이므로 else문으로 빠진다.

객체에 문자열을 key값으로 하고 i값을 value로 하여 추가한다.

그리고 누적할 배열의 i번째 방, 즉 0번째 방에 [현재 문자, 개수 초기값 = 1]의 형태로 push한다.

(그리고 i값을 1증가시키면 첫번째 문자와 중복되지 않는 다른 문자는 1번 방에 저장된다.)

 

5. 검사하는 문자가 이미 기존에 등록된 문자라면 (배열의 해당 인덱스 방에 존재한다면) 해당 배열방의 숫자를 1 증가시킨다.

 

위 과정을 반복하면 

char 객체의 형태는 { m: 0, i: 1, s: 2, p: 3 } 이런 식이 되고,

count 배열의 형태는 [ [ 'm', 1 ], [ 'i', 4 ], [ 's', 4 ], [ 'p', 2 ] ] 이런 식이 된다.

 

6. 원하는 형태를 만들었으므로 sort 함수를 사용하여 정렬한다.