알고리즘 문제풀이 5

문자열 내에서 문자들의 사용빈도와 정렬이 복합된 문제이다.
빈도수 파악을 위한 반복문과 객체의 활용, 그리고 sort 정렬 메소드를 잘 활용하면 되는 문제

/*
 *  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]
 *  ]
 *
 *       :: Example2 ::
 *
 *  characterFrequency('miaaiaaippi') ===
 *  [
 *    ['a', 4],
 *    ['i', 4],
 *    ['p', 2],
 *    ['m', 1]
 *  ]
 *
 *       :: Example3 ::
 *
 *  characterFrequency('mmmaaaiiibbb') ===
 *  [
 *    ['a', 3],
 *    ['b', 3],
 *    ['i', 3],
 *    ['m', 3]
 *  ]
 *
 */

var characterFrequency = function (string) {
  //처음에 바로 배열로 접근하려고 하니 알파벳 정렬에서 걸렸다. 
  //그래서 처음에는 객체로 만들고, 그다음에 배열로 접근하니 문제가 해결되었다.
  let result_obj = {};
  let key_arr = [];
  
  for (let i = 0; i < string.length; i++) {
    if (!Object.keys(result_obj).includes(string[i])) {
      //해당 부분을 result_obj[string[i]] ===undefined 로 조건을 걸어주어도 된다.
      //객체 내에 해당 문자가 없으면 객체와 배열에 각각 해당 문자 넣어주기.
      key_arr.push(string[i]);
      result_obj[string[i]] = 1;
    } else {
      result_obj[string[i]]++;
    }
  }
  let newKey = key_arr.sort();
  //문자들을 순서대로 정렬해주기
  let result = [];
  for (let t = 0; t < newKey.length; t++) {
    let freq_arr = [];
    //0번째 인덱스에는 문자가 그리고 1번째 인덱스에는 해당 문자의 빈도수가 들어가면된다.
    freq_arr[0] = newKey[t];
    freq_arr[1] = result_obj[newKey[t]];
    result.push(freq_arr);
  }
  //위의 반복문은 문자열 순서대로 정렬해 주는 것이면, 
  //이번 반복문은 빈도 수가 큰 순서대로 재정렬 해주는 것이다. -> 삽입정렬 활용
  for (let j = 0; j < result.length; j++) {
    for (let k = 0; k < result.length - 1; k++) {
      //버블정렬을 사용해 준다면, result.length-1 보다는 result.length-j 가 
      //더 효율적이다.
      //왜냐면 한바퀴 돌때마다 가장 큰값들을 맨뒤로 보내주기 때문에 다음 반복때는
      //그 뒤에 값들까지 가지 않아도 되기 때문이다.
      if (result[k][1] < result[k + 1][1]) {
        let big_num = result[k + 1];
        result[k + 1] = result[k];
        result[k] = big_num;
      }
    }
  }
  return result;
};

내코드는 빈도수 체크에 있어서는 동기 분들과 방식이 유사하다.
약간의 차이에 대해서 정리해보고자 한다.

1) 객체로 빈도수를 체크한 다음, 그 객체를 for in 문으로 돌면서 이중배열로 만들어주기.
이 때 이중 배열의 1번째 인덱스 같은 경우에, 아래의 코드처럼 이중배열 내에 push 해주는 방식으로도
가능하다.
-> 해당 방법은 시간복잡도에 있어서는 효율적이나, 객체를 만들어줌으로써 공간복잡도에서 비효율이다.

let result = [];

for (key in obj) {
    let innerArray = [];
    innerArray.push(key);
    innerArray.push(obj[key]);
    result.push(innerArray);
}

2) 아예 for문을 돌때 이중배열을 바로 만들어준다.
-> 해당 방법은 시간복잡도에 있어서는 위의 방법이 2N인에 반해, N^2이다. 즉 비효율이다.
하지만 객체를 만들고 이중배열을 만드는 것이 아니라 바로 이중배열을 만들어줘서 공간복잡도에서 효율적이다.

var characterFrequency = function (string) {
  let result = []
  for (let i = 0; i < string.length; i++) {
    let char = string[i]
    let flag = false
    let j
    for (j = 0; j < result.length; j++) {
      if (result[j].indexOf(char) !== -1) {
        flag = true
        break
      }
    }
    if (flag === false) {
      result.push([char, 1])
    } else {
      result[j][1]++
    }
  }
}

가장 핵심은 sort()부분이다. 나는 문자 오름차순과 빈도수 내림차순을 따로 구현해주었지만,
sort() 메소드를 잘 활용해 준다면 바로 구현할 수 있다.
array.sort() MDN 설명 문서

array.sort(function(a,b))에서 sort안에 들어가는 함수는
자연스레 앞의 요소와 뒤의 요소를 빼준다. a를 임의로 더 작은수, b가 비교적 더 큰수라고 가정한 함수이다. 오름차순의 경우, 앞의요소에서 뒤의요소를 빼서 음수가 나오면 앞의 요소가 작은 것이기 때문에 앞에 온다는 것!
그렇다면 내림차순을 하려면? 뒤의 요소에서 앞의 요소를 빼주는 함수값을 실행해주면 된다.

즉, 정리하자면
array.sort((function(a,b))를 실행했을 때,
1) 오름차순을 구현하려는 경우

 array.sort((function(a,b){
   return a-b
 } //혹은
 array.sort((function(a,b){
   if(a<b){
    return -1
 }

위아래의 두 코드가 다른 코드 같지만, 그 의미는 앞의 수가 뒤의 수보다 더 작다는 의미이다.
위에서 설명한대로 sort 메소드는 자연스럽게 앞의 수에서 뒤의 수를 빼고 음수면, 앞의 수가 더 작으니까 더 앞으로 오게 된다. 더 작은 수가 인자로서 앞에 오게 놓았기 때문에 오름차순을 구현한다고 생각했다.

2)내림차순을 구현하려는 경우

 array.sort((function(a,b){
   return b-a
 } //혹은
 array.sort((function(a,b){
   if(a>b){
    return -1
 }

정확히 오름차순을 구현하려는 경우와 반대로, 인자들을 배치하면 된다.
뒤에 위치한 인자가 더 작다라는 의미를 가지므로, 즉 작은 수가 뒤에 오는 내림차순을 구현한다고 생각했다.

이를 활용하여 내림차순 오름차순을 구현할 수 있다.

result.sort(function (a, b) {
   //여기서 a,b는 result라는 배열 내에서 임의의 연속된 앞과 뒤의 요소이다.
    if (a[1] !== b[1]) {
      // 각 요소는 이중배열이고, 1번째 인덱스에 빈도수가 포함되어있다.
      //따라서 빈도수가 다르면,
      return b[1] - a[1]; 
      // 더 큰 frequency를 더 앞의 index에 배치한다. (내림차순)
      //숫자를 비교할때는 이렇게 함수 안에 빼주는 요소의 위치를 바꿔주면서 내림차순 오름차순 조정가능
    } else {
      // frequency가 같으면,
      if (a[0] < b[0]) {
        // 뒤의 character가 앞의 character보다 뒤에 들어가야 할 알파벳이라면,
        // character를 알파벳 순서로 정렬한다. (오름차순)
        return -1;
        //문자열 뿐 아니라 숫자 비교할때도 이와 같이 if문을 통해, 오름차순 내림차순 조정가능하다. 
        //즉 뒤의 문자가 더 커서 return -1을 하는 경우는 오름차순
        //반대로 뒤의 요소(b)가 더 커서 return 1을 하는 경우는 내림차순이다.
      }
    }
  });

이러한 sort()를 삼항연산자로도 표현 가능하다

result.sort(function (a, b) {
	return (a[1] > b[1]) 
      ? -1 //(빈도수 내림차순 하겠다)
   	  : ((a[1] < b[1]) 
       		? 1 
       		:((a[0] < b[0])
         		? -1 
         		: ((a[0] > b[0]) 
            		? 1 
            		: 0)))
})